题目链接：http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemId=649 BFS，不解释
  view code
1 #include <iostream>
2 #include <cstdio>
3 #include <cstdlib>
4 #include <cstring>
5 #include <cmath>
6 #include <algorithm>
7 #include <queue>
8 using namespace std;
9 int map[210][210], n, m;
10 char s[210][210];
11 struct nod{
12 int x, y;
13 }S, T;
14 const int dir[4][2] = {{1, 0}, {0, 1}, {-1, 0}, {0, -1}};
15 queue<nod> Q;
16 void init(){
17 for (int i = 0; i < n; i++)
18 for (int j = 0; j < m; j++){
19 if (s[i][j] == 'r') {S.x = i; S.y = j;}
20 if (s[i][j] == 'a') {T.x = i; T.y = j;}
21 }
22 memset(map, -1, sizeof(map));
23 }
24 bool inMap(int x, int y){
25 return x >= 0 && x < n && y >= 0 && y < m;
26 }
27 void bfs(){
28 map[S.x][S.y] = 0;
29 Q.push(S);
30 nod u, v;
31 while (!Q.empty()){
32 u = Q.front();
33 Q.pop();;
34 for (int i = 0; i < 4; i++){
35 v.x = u.x + dir[i][0];
36 v.y = u.y + dir[i][1];
37 if (!inMap(v.x, v.y) || s[v.x][v.y] == '#') continue;
38 if ((s[v.x][v.y] == '.' || s[v.x][v.y] == 'a') && (map[u.x][u.y] + 1 < map[v.x][v.y] || map[v.x][v.y] == -1)){
39 map[v.x][v.y] = map[u.x][u.y] + 1;
40 Q.push(v);
41 }
42 if (s[v.x][v.y] == 'x' && (map[u.x][u.y] + 2 < map[v.x][v.y] || map[v.x][v.y] == -1)){
43 map[v.x][v.y] = map[u.x][u.y] + 2;
44 Q.push(v);
45 }
46 }
47 }
48 }
49 int main(){
50 while (~scanf("%d%d", &n, &m)){
51 for (int i = 0; i < n; i++) scanf("%s", s[i]);
52 init();
53 bfs();
54 if (map[T.x][T.y] == -1){
55 printf("Poor ANGEL has to stay in the prison all his life.\n");
56 continue;
57 }
58 printf("%d\n", map[T.x][T.y]);
59 }
60 return 0;
61
|