HDU 1242

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