HDU 1242 Rescue

 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\n", 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.\n");
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 }