转弯次数不超过两次。和前段时间做的cf那题几乎一样，我又贴一遍。。。最近好懈怠，不想写题。
#include<cstdio> #include<cstring> #include<algorithm> #include<iostream> #include<string> #include<cmath> #include<queue> #include<limits.h> #define CLR(a,b) memset((a),(b),sizeof((a))) using namespace std; typedef long long ll; const int N = 1001; int n, m; int sx, sy, ex, ey; int flag; int s[N][N]; bool vis[N][N][3][3]; bool check(int x, int y) { if(s[x][y] == 0 || x == ex && y == ey) return true; return false; } void dfs(int x, int y, int d, int turn) {//上下：d = 1，左右：d = 2 if(turn > 2 || vis[x][y][d][turn]) return; if(x == ex && y == ey) { flag = true; return; } vis[x][y][d][turn] = 1; if(x-1 >= 1 && !vis[x-1][y][1][turn+(d==2)]) { if(check(x-1,y)) dfs(x-1, y, 1, turn + (d==2)); } if(x+1 <= n && !vis[x+1][y][1][turn+(d==2)]) { if(check(x+1,y)) dfs(x+1, y, 1, turn + (d==2)); } if(y-1 >= 1 && !vis[x][y-1][2][turn+(d==1)]) { if(check(x,y-1)) dfs(x, y-1, 2, turn + (d==1)); } if(y+1 <= m && !vis[x][y+1][2][turn+(d==1)]) { if(check(x,y+1)) dfs(x, y+1, 2, turn + (d==1)); } } int main() { int i, j; while(~scanf("%d%d", &n, &m) , n && m) { for(i = 1; i <= n; ++i) { for(j = 1; j <= m; ++j) { scanf("%d", &s[i][j]); } } int t = 0; scanf("%d", &t); while(t--){ flag = 0; CLR(vis, 0); scanf("%d%d%d%d", &sx, &sy, &ex, &ey); if(s[sx][sy] == s[ex][ey] && s[sx][sy] != 0) dfs(sx, sy, 0, 0); else {printf("NO ");continue;} if(flag) puts("YES"); else puts("NO"); } } return 0; }