Rescue

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<cstring>
 4 #include<queue>
 5 #define MAX_N 205
 6 using namespace std;
 7 struct Node
 8 {
 9     int x,y,t;
10     bool operator<(const Node &a)const
11     {
12         return t>a.t;
13     }
14 };
15 
16 Node start;
17 
18 char map[MAX_N][MAX_N];
19 
20 int dir[][2]={{0,1},{0,-1},{1,0},{-1,0}};
21 
22 int n,m;
23 
24 int bfs()
25 {
26     priority_queue<Node> que;
27     Node cur,next;
28     int i,j;
29     map[start.x][start.y]=‘#‘;
30     que.push(start);
31     while(!que.empty())
32     {
33         cur=que.top();
34         que.pop();
35         for(i=0;i<4;i++)
36         {
37             next.x=cur.x+dir[i][0];
38             next.y=cur.y+dir[i][1];
39             next.t=cur.t+1;
40 
41             if(next.x<0||next.x>=n||next.y<0||next.y>=m)
42                 continue;
43             if(map[next.x][next.y]==‘#‘)
44                 continue;
45             if(map[next.x][next.y]==‘r‘)
46                 return next.t;
47             if(map[next.x][next.y]==‘x‘)
48             {
49                 next.t++;
50                 map[next.x][next.y]=‘#‘;
51                 que.push(next);
52             }
53             else if(map[next.x][next.y]==‘.‘)
54             {
55                 map[next.x][next.y]=‘#‘;
56                 que.push(next);
57             }
58         }
59     }
60     return -1;
61 }
62 
63 int main()
64 {
65    // freopen("a.txt","r",stdin);
66     int i,ans;
67     char *p;
68     while(scanf("%d%d",&n,&m)!=EOF)
69     {
70         for(i=0;i<n;i++)
71         {
72             scanf("%s",map[i]);
73             if(p=strchr(map[i],‘a‘))
74             {
75                 start.x=i;
76                 start.y=p-map[i];
77                 start.t=0;
78             }
79         }
80         ans=bfs();
81 
82         printf(ans+1?"%d\n":"Poor ANGEL has to stay in the prison all his life.\n",ans);
83     }
84     return 0;
85 }