简单变形的广搜，而HDU 1026 Ignatius and the Princess I 是这道题的升级版，因为每个格子停留的时间可能不相同。
这里，天使的朋友可能有多个，所以我们从天使开始逆向去找他的朋友，最先找到他的朋友就是最短时间。
题目的变形在于多了守卫，每当一个守卫进入队列，第一次只扩展当前位置，仅仅是时间加1，第二次再向四个方向扩展。
1 //#define LOCAL 2 #include <iostream> 3 #include <cstdio> 4 #include <cstring> 5 #include <queue> 6 using namespace std; 7 8 struct Point 9 { 10 int x, y; 11 int steps; 12 }start; 13 14 int row, col; 15 int dir[4][2] = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}}; 16 int vis[205][205]; 17 char map[205][205]; 18 19 void BFS(void) 20 { 21 queue<Point> qu; 22 start.steps = 0; 23 qu.push(start); 24 while(!qu.empty()) 25 { 26 Point fir = qu.front(); 27 if(map[fir.x][fir.y] == 'r') 28 { 29 printf("%d ", fir.steps); 30 return; 31 } 32 if(map[fir.x][fir.y] == 'x') 33 {//第一次停留在原地 34 Point next; 35 next.x = fir.x, next.y = fir.y, next.steps = fir.steps + 1; 36 map[fir.x][fir.y] = '.';//记得改变'x'，下一次变开始向四周扩展 37 qu.push(next); 38 qu.pop(); 39 continue; 40 } 41 for(int i = 0; i < 4; ++i) 42 { 43 int xx = fir.x + dir[i][0]; 44 int yy = fir.y + dir[i][1]; 45 if(xx<0 || xx>=row || yy<0 || yy>=col || vis[xx][yy] || map[xx][yy]=='#') 46 continue; 47 else 48 { 49 Point next; 50 next.x = xx, next.y = yy, next.steps = fir.steps + 1; 51 vis[xx][yy] = 1; 52 qu.push(next); 53 } 54 } 55 qu.pop(); 56 } 57 printf("Poor ANGEL has to stay in the prison all his life. "); 58 } 59 60 int main(void) 61 { 62 #ifdef LOCAL 63 freopen("1242in.txt", "r", stdin); 64 #endif 65 66 while(scanf("%d%d", &row, &col) == 2) 67 { 68 getchar(); 69 for(int i = 0; i < row; ++i) 70 { 71 for(int j = 0; j < col; ++j) 72 { 73 scanf("%c", &map[i][j]); 74 if(map[i][j] == 'a') 75 start.x = i, start.y = j; 76 } 77 getchar(); 78 } 79 80 memset(vis, 0, sizeof(vis)); 81 map[start.x][start.y] = '#'; 82 vis[start.x][start.y] = 1; 83 BFS(); 84 } 85 return 0; 86 }