hdu 1026 Ignatius and the Princess I (bfs+记录路径)（priority_queue）

  1 #include<iostream>
  2 #include<queue>
  3 #include<cstdio>
  4 
  5 using namespace std;
  6 
  7 struct node{
  8     int x,y;
  9     int time;
 10     friend bool operator < (node a,node b){//优先队列！！
 11         return a.time > b.time;
 12     }
 13 };
 14 
 15 struct M{
 16     char data;
 17     int prex,prey;
 18     int time;
 19 }map[102][102];
 20 
 21 int n,m;
 22 int dir[4][2]={1,0,-1,0,0,1,0,-1};
 23 
 24 bool isInMap(int x,int y){
 25     return x>=0&&x<n&&y>=0&&y<m;
 26 }
 27 
 28 int bfs(){
 29     node cur,next;
 30     priority_queue<node> q;
 31     cur.x = 0;
 32     cur.y = 0;
 33     cur.time = 0;
 34     map[0][0].data = ‘X‘;
 35     q.push(cur);
 36     while(!q.empty()){
 37         cur = q.top();
 38         q.pop();
 39         if(cur.x == n-1 && cur.y == m-1)
 40             return cur.time;
 41         for(int i=0;i<4;i++){
 42             int xx = cur.x + dir[i][0];
 43             int yy = cur.y + dir[i][1];
 44             if(isInMap(xx,yy) && map[xx][yy].data == ‘.‘){
 45                 next.x = xx;
 46                 next.y = yy;
 47                 next.time = cur.time+1;
 48                 map[xx][yy].prex = cur.x;
 49                 map[xx][yy].prey = cur.y;
 50                 map[xx][yy].time = 0;
 51                 map[xx][yy].data = ‘X‘;
 52                 q.push(next);
 53             }
 54             else if(isInMap(xx,yy) && map[xx][yy].data!=‘X‘){
 55                 next.x = xx;
 56                 next.y = yy;
 57                 next.time = cur.time + (map[xx][yy].data-‘0‘) + 1;//记得加上通过时间
 58                 map[xx][yy].prex = cur.x;
 59                 map[xx][yy].prey = cur.y;
 60                 map[xx][yy].time = map[xx][yy].data-‘0‘;
 61                 map[xx][yy].data = ‘X‘;
 62                 q.push(next);
 63             }
 64         }
 65     }
 66     return -1;
 67 }
 68 
 69 void printPath(int x,int y,int time){
 70     if(time>0){
 71         if(map[x][y].time--){
 72             printPath(x,y,time-1);
 73             printf("%ds:FIGHT AT (%d,%d)\n",time--,x,y);
 74         }
 75         else{
 76             printPath(map[x][y].prex,map[x][y].prey,time-1);
 77             printf("%ds:(%d,%d)->(%d,%d)\n",time--,map[x][y].prex,map[x][y].prey,x,y);
 78         }
 79     }
 80     return ;
 81 }
 82 
 83 int main(){
 84     while(cin>>n>>m){
 85         for(int i=0;i<n;i++){
 86             getchar();
 87             for(int j=0;j<m;j++){
 88                 scanf("%c",&map[i][j].data);
 89             }
 90         }
 91         int time = bfs();
 92         if(time>=0){
 93         printf("It takes %d seconds to reach the target position, let me show you the way.\n",time);
 94         printPath(n-1,m-1,time);
 95         }
 96         else{
 97             printf("God please help our poor hero.\n");
 98         }
 99         printf("FINISH\n");
100     }
101     return 0;
102 }