bfs 本题要点： 1、连连看，先保证起点和终点，都不是0，且相等。 2、然后从起点 s 开始bfs, 用 step 记录拐弯次数。拐弯不超过两次。 3、direction 表示，进入点 (x, y) ，是从哪个方向进来的。 比如某一点 (x, y), 它的 direction == 0, 表示 (x, y)的上一点 是 从 左右方向进入 (x, y)。 此时，点(x, y) 的下一点，只需要从上下方向寻找。 4、点(x, y) 沿着上方向，一直走，直到不能走为止。所谓不能走，就是说，遇到非空白的地方。 当遇到 终点 t，表示可以找到一条路径（拐弯次数不超过2次）， 从s到t。 代码较长，其中四个方向都是类似的代码。
#include <cstdio> #include <cstring> #include <iostream> #include <queue> using namespace std; const int MaxN = 1010; int n, m, query; int mp[MaxN][MaxN]; bool vis[MaxN][MaxN]; struct node { int x, y, step; int direction; //direction 表示，进入点 (x, y) ，是从哪个方向进来的 }; // direction == 0, 表示从 左右方向; direction == 0 表示从上下方向。 direction == -1， 表示点(x, y) 是起点 node s, t; bool judge(int x, int y) { return x >= 1 && x <= n && y >= 1 && y <= m; } void bfs() { for(int i = 0; i <= n; ++i) for(int j = 0; j <= m; ++j) vis[i][j] = false; int ax, ay; node tmp; s.step = -1, s.direction = -1; queue<node> q; q.push(s); vis[s.x][s.y] = true; while(q.size()) { node now = q.front();q.pop(); ax = now.x, ay = now.y; if(now.step >= 2) continue; if(now.direction == -1 || now.direction == 1)// 往左，右 { ax = now.x, ay = now.y; while(true) // 往左 { if(judge(ax, ay - 1) == false) break; if(!(ax == t.x && ay - 1 == t.y) && mp[ax][ay - 1] == 0) { if(vis[ax][ay - 1] == false) { vis[ax][ay - 1] = true; tmp.x = ax, tmp.y = ay - 1, tmp.direction = 0, tmp.step = now.step + 1; q.push(tmp); } }else{ if(ax == t.x && ay - 1 == t.y) { printf("YES\n"); return; } break; } --ay; } ax = now.x, ay = now.y; while(true) { if(judge(ax, ay + 1) == false) break; if(!(ax == t.x && ay + 1 == t.y) && mp[ax][ay + 1] == 0) { if(vis[ax][ay + 1] == false) { vis[ax][ay + 1] = true; tmp.x = ax, tmp.y = ay + 1, tmp.direction = 0, tmp.step = now.step + 1; q.push(tmp); } }else{ if(ax == t.x && ay + 1 == t.y) { printf("YES\n"); return; } break; } ++ay; } } //往上，下 if(now.direction == -1 || now.direction == 0) { ax = now.x, ay = now.y; while(true) // 上 { if(judge(ax - 1, ay) == false) break; if(!(ax - 1 == t.x && ay == t.y) && mp[ax - 1][ay] == 0) { if(vis[ax - 1][ay] == false) { vis[ax - 1][ay] = true; tmp.x = ax - 1, tmp.y = ay, tmp.direction = 1, tmp.step = now.step + 1; q.push(tmp); } }else{ if(ax - 1 == t.x && ay == t.y) { printf("YES\n"); return; } break; } --ax; } ax = now.x, ay = now.y; while(true) // 下 { if(judge(ax + 1, ay) == false) break; if(!(ax + 1 == t.x && ay == t.y) && mp[ax + 1][ay] == 0) { if(vis[ax + 1][ay] == false) { vis[ax + 1][ay] = true; tmp.x = ax + 1, tmp.y = ay, tmp.direction = 1, tmp.step = now.step + 1; q.push(tmp); } }else{ if(ax + 1 == t.x && ay == t.y) { printf("YES\n"); return; } break; } ++ax; } } } printf("NO\n"); } int main() { while(scanf("%d%d", &n, &m) != EOF) { if(0 == n && 0 == m) break; for(int i = 1; i <= n; ++i) { for(int j = 1; j <= m; ++j) { scanf("%d", &mp[i][j]); } } scanf("%d", &query); for(int i = 0; i < query; ++i) { scanf("%d%d%d%d", &s.x, &s.y, &t.x, &t.y); if(mp[s.x][s.y] == 0 || mp[t.x][t.y] == 0 || (mp[s.x][s.y] != mp[t.x][t.y])) { printf("NO\n"); }else bfs(); } } return 0; } /* 3 4 1 2 3 4 0 0 0 0 4 3 2 1 4 1 1 3 4 1 1 2 4 1 1 3 3 2 1 2 4 3 4 0 1 4 3 0 2 4 1 0 0 0 0 2 1 1 2 4 1 3 2 3 0 0 */ /* YES NO NO NO NO YES */