HDU1242 Rescue

 1 /*by SilverN*/
 2 #include<iostream>
 3 #include<algorithm>
 4 #include<cstring>
 5 #include<cstdio>
 6 #include<queue>
 7 #include<cmath>
 8 using namespace std;
 9 const int INF=300000;
10 const int mxn=300;
11 struct node{
12     int x,y;
13     int w;//用时 
14 };
15 queue<node>q;
16 int mx[5]={0,1,0,-1,0},
17     my[5]={0,0,1,0,-1};
18 int ax,ay;
19 char mp[mxn][mxn];
20 int ans[mxn][mxn];
21 int n,m;
22 
23 void BFS(node s){
24     q.push(s);
25     int i;
26     node hd;
27     while(!q.empty()){
28         hd=q.front();
29         q.pop();
30         for(i=1;i<=4;i++){
31             int x=hd.x+mx[i];
32             int y=hd.y+my[i];
33             if(x>0 && x<=n && y>0 && y<=m && mp[x][y]!=‘#‘){
34                 node v;
35                 v.x=x; v.y=y; v.w=hd.w+1;
36                 if(mp[x][y]==‘x‘) v.w++;//杀死守卫要多花时间 
37                 if(v.w<ans[x][y]){
38                     ans[x][y]=v.w;
39                     q.push(v);
40                 }
41             }
42         }
43     }
44     return;
45 }
46 int main(){
47     int i,j;
48     while(scanf("%d%d",&n,&m)!=EOF){
49         memset(mp,‘ ‘,sizeof(mp));
50         int sx,sy;
51         node ST;
52         for(i=1;i<=n;i++){
53             scanf("%s",mp[i]+1);
54             for(j=1;j<=m;j++){
55                 ans[i][j]=INF;
56                 if(mp[i][j]==‘a‘){ax=i;ay=j;}
57                 else if(mp[i][j]==‘r‘){sx=i;sy=j;}
58                 else if(mp[i][j]!=‘.‘ && mp[i][j]!=‘x‘)mp[i][j]=‘#‘;
59                 //从讨论区看到数据里可能有其他符号，也应算作# 
60             }
61         }
62         ST.x=sx;ST.y=sy;ST.w=0;
63         ans[sx][sy]=0;
64         BFS(ST);
65         if(ans[ax][ay]!=INF)printf("%d\n",ans[ax][ay]);//有解 
66         else printf("Poor ANGEL has to stay in the prison all his life.\n");//无解 
67     }
68     return 0;
69 }