1 /*
2 zju 1649 ,hdu 1242 最短路径 BFS
3 ymc 2008/9/17
4 题目大意：
5 在一个n×m的地图上，天使用a表示，天使的一些朋友用r表示。＃表示墙，.表示路。
6 x表示有一个守卫。r可以上下左右移动，每次只能移动一个点，需要1的时间。如果移到
7 x的位置，需要额外1的时间杀掉x。
8 求从r到a的最小时间
9 解题思路：
10 求所有r到其它点的的最短距离。
11 dist[i][j]记录所有r到点i,j的最短距离，所有r的dist为0.
12 used标记点i，j的最短距离是否已经求出。用BFS搜索a的距离。
13
14 */
15 #include <iostream>
16 #include <queue>
17 using namespace std;
18 const int N=300;
19 int dist[N][N];
20 char graph[N][N];
21 int step[4][2]={{1,0},{-1,0},{0,1},{0,-1}};
22 struct Pt
23 {
24 int x,y;
25 int d;
26 Pt(int xx=0,int yy=0,int dd=-1)
27 {
28 x=xx;y=yy;d=dd;
29 }
30 bool operator<(const Pt &p)const
31 {
32 return d>p.d;
33 }
34 };
35 int n,m;
36 int ax,ay;
37 void BFS()
38 {
39
40 priority_queue<Pt> q;
41 for(int i=0;i<n;i++)
42 for(int j=0;j<m;j++)
43 {
44 dist[i][j]=-1;
45 if(graph[i][j]=='a')
46 {
47 ax=i;ay=j;
48 }
49 else if(graph[i][j]=='r')
50 {
51 q.push(Pt(i,j,0));
52 dist[i][j]=0;
53 }
54 }
55 Pt u;
56 int x1,y1;
57 while(!q.empty())
58 {
59 u=q.top();
60 q.pop();
61 if(u.x==ax && u.y== ay)
62 return ;
63 for(int k=0;k<4;k++)
64 {
65 x1=u.x+step[k][0];
66 y1=u.y+step[k][1];
67 if(x1<0||x1>=n||y1<0||y1>=m)
68 continue;
69 if(dist[x1][y1]>=0||graph[x1][y1]=='#')
70 continue;
71 if(graph[x1][y1]=='x')
72 dist[x1][y1]=dist[u.x][u.y]+2;
73 else
74 dist[x1][y1]=dist[u.x][u.y]+1;
75 q.push(Pt(x1,y1,dist[x1][y1]));
76 }
77 }
78 }
79 int main()
80 {
81 while(cin>>n>>m)
82 {
83 for(int i=0;i<n;i++)
84 for(int j=0;j<m;j++)
85 cin>>graph[i][j];
86 BFS();
87 if(dist[ax][ay]>=0)
88 cout<<dist[ax][ay]<<endl;
89 else
90 cout<<"Poor ANGEL has to stay in the prison all his life."<<endl;
91 }
92 }