Online Judge | Problem Set | Authors | Online Contests | User | ||||||
---|---|---|---|---|---|---|---|---|---|---|
Web Board Home Page F.A.Qs Statistical Charts | Current Contest Past Contests Scheduled Contests Award Contest |
172K 0ms AC#include <iostream> #include <stdio.h> using namespace std; bool qiang[110][110] = {false}; bool dfsUsed[110][110] = {false}; bool used[110][110][4] = {false}; bool zdrkl = false;//找到入口了 int rkX, rkY, rkFx; int offset[4][2] = {{1, 0}, {0, -1}, {-1, 0}, {0, 1}}; int N, M; bool isCourTYard(int x, int y){ if(x > 0 && y > 0 && !qiang[x-1][y] && !qiang[x][y-1] && !qiang[x-1][y-1]) return true; if(x > 0 && y <= M && !qiang[x-1][y] && !qiang[x][y+1] && !qiang[x-1][y+1]) return true; if(x <= N && y > 0 && !qiang[x+1][y] && !qiang[x][y-1] && !qiang[x+1][y-1]) return true; if(x <= N && y <= M && !qiang[x+1][y] && !qiang[x][y+1] && !qiang[x+1][y+1]) return true; return false; } bool dfs(int x, int y){ if(zdrkl) return true; if(x > 0 && x <= N && qiang[x-1][y] && qiang[x+1][y]){ zdrkl = true; rkX = x; rkY = y; if(y > 0 && dfsUsed[x][y-1]) rkFx = 1; else rkFx = 3; return true; } if(y > 0 && y <= M && qiang[x][y-1] && qiang[x][y+1]){ zdrkl = true; rkX = x; rkY = y; if(x > 0 && dfsUsed[x-1][y]) rkFx = 2; else rkFx = 0; } dfsUsed[x][y] = 1; if(x > 0 && !qiang[x-1][y] && !dfsUsed[x-1][y]){ if(dfs(x-1, y)) return true; } if(x <= N && !qiang[x+1][y] && !dfsUsed[x+1][y]){ if(dfs(x+1, y)) return true; } if(y > 0 && !qiang[x][y-1] && !dfsUsed[x][y-1]){ if(dfs(x, y-1)) return true; } if(y <= M && !qiang[x][y+1] && !dfsUsed[x][y+1]){ if(dfs(x, y+1)) return true; } return false; } int main() { scanf("%d%d", &N, &M); char s[200]; for(int i = 1; i <= N; i++){ scanf("%s", s); for(int j = 1; j <= M; j++){ char c = s[j-1]; if(c == '#') qiang[i][j] = true; } } dfs(0,0); //cout << rkX << " " << rkY << " " << rkFx; int fx = rkFx, x = rkX, y = rkY; while(1){ //cout << x << " " << y << " " << fx << endl; int FX; for(FX = (fx+1)%4; ; FX = (FX+1)%4){ if(!qiang[x+offset[FX][0]][y+offset[FX][1]]) break; } if(used[x][y][FX]){ printf("NO\n"); return 0; } used[x][y][FX] = true; fx = (FX+2)%4; x += offset[FX][0]; y += offset[FX][1]; //cout << x << " " << y << " " << fx << endl; if(x == rkX && y == rkY){ printf("NO\n"); return 0; } if(isCourTYard(x, y)){ printf("YES\n"); return 0; } } return 0; } Followed by: Post your reply here: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator