题目描述:
Time Limit: 20000/10000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Others)
Total Submission(s): 53936 Accepted Submission(s): 13670
#include<bits/stdc++.h> using namespace std; typedef long long ll; const int maxn = 1005; int m, n; int maze[maxn][maxn]; int dx[4] = { -1,1,0,0 }; int dy[4] = { 0,0,-1,1 }; bool vis[maxn][maxn]; bool check(int x, int y) { return x >= 1 && x <= m && y >= 1 && y <= n && !vis[x][y]; } pair<int, int>s, e; bool dfs(int x,int y,int pre,int last) { vis[x][y] = 1; if (last == 0 && (x != e.first && y != e.second)) { return false; }//剪枝,最后一次方向旋转后,判断终点与当前点是否在一个方向 for (int d = 0; d < 4; d++) { int tx = x + dx[d]; int ty = y + dy[d]; if (check(tx, ty)) { if (maze[tx][ty] == 0) { if (d == pre) { if (dfs(tx, ty, d, last))return true; } else if(last>0){ if (dfs(tx, ty, d, last - 1))return true; } } else if ((d == pre||last>0)&&tx==e.first&&ty==e.second) {return true;} } } return false; } int main() { //freopen("test.txt", "r", stdin); while (scanf("%d%d", &m, &n) && n) { for (int i = 1; i <= m; i++) { for (int j = 1; j <= n; j++) { scanf("%d", &maze[i][j]); } } int k; scanf("%d", &k); while (k--) { scanf("%d%d%d%d", &s.first, &s.second, &e.first, &e.second); if (maze[s.first][s.second] != maze[e.first][e.second]) { printf("NO\n"); continue; } bool f = 0; for (int d = 0; d < 4; d++) {//四个方向出发 memset(vis, 0, sizeof(vis)); if (dfs(s.first, s.second, d, 2)) { f = 1; printf("YES\n"); break; } } if(!f)printf("NO\n"); } } return 0; }
原文:https://www.cnblogs.com/MYMYACMer/p/14588202.html