这是个简单的广搜题，注意下一下细节都能写出来， 大多数人都少考虑了一点，就是 假如 我的起始点就有一个机关， 并且不是 1 号机关，
这样的话是无结果的。不懂的可以测试一下代码下面的数据
#include<stdio.h> #include<iostream> #include<stack> #include<queue> #include<math.h> #include<stdlib.h> #include<cstring> using namespace std; #define Max(a,b) (a>b?a:b) #define Min(a,b) (a<b?a:b) #define INF 0xfffffff #define maxn 110 struct Point { int x, y, step; }B[maxn]; char maps[maxn][maxn]; bool vis[maxn][maxn]; int dir[8][2] = { {-1,-1},{-1,1},{1,-1},{1,1},{-1,0},{1,0},{0,-1},{0,1}}; int n, m, k; bool OK(Point P,int i,int End) { if(P.x >= 0 && P.x < n && P.y >= 0 && P.y < m && maps[P.x][P.y] != '#' && maps[P.x][P.y] <= End+'0' && !vis[P.x][P.y]) { if(i < 4) { if(i == 0 && maps[P.x+1][P.y] == '#' && maps[P.x][P.y+1] == '#') return false; if(i == 1 && maps[P.x+1][P.y] == '#' && maps[P.x][P.y-1] == '#') return false; if(i == 2 && maps[P.x-1][P.y] == '#' && maps[P.x][P.y+1] == '#') return false; if(i == 3 && maps[P.x-1][P.y] == '#' && maps[P.x][P.y-1] == '#') return false; } return true; } return false; } int BFS(int Star,int End) { Point P, Pn; queue<Point> Q; memset(vis, false, sizeof(vis)); Q.push(B[Star]); if(B[End].x == B[0].x && B[End].y == B[0].y && End != 1) return -1; while( !Q.empty() ) { P = Q.front(); Q.pop(); if(P.x == B[End].x && P.y == B[End].y) return P.step; for(int i=0; i<8; i++) { Pn.x = P.x + dir[i][0]; Pn.y = P.y + dir[i][1]; Pn.step = P.step + 1; if( OK(Pn,i, End) ) { vis[Pn.x][Pn.y] = true; Q.push(Pn); } } } return -1; } int main() { int T, i; cin >> T; while(T--) { cin >> n >> m >> k; for(i=0; i<n; i++) scanf("%s", maps[i]); for(i=0; i<=k; i++) { cin >> B[i].x >> B[i].y; B[i].x --, B[i].y --; B[i].step = 0; maps[B[i].x][B[i].y] = i + '0'; } int ans, sum; ans = sum = 0; for(i=0; i<k; i++) { ans = BFS(i, i+1); if(ans == -1) break; sum += ans; } if( k == i) printf("%d\n", sum); else printf("-1\n"); } return 0; } /* 3 3 3 2 ... #.. ... 1 1 1 2 1 1
答案 -1 */