1 //由于本題要輸出最短時間，所以要用優先隊列，喲西 
  2 #include<iostream>
  3 #include<stdio.h>
  4 #include<functional>
  5 using namespace std;
  6 #include<queue>
  7 struct Node
  8 {
  9     friend bool operator<(Node n1,Node n2)
 10     {
 11         return n1.t > n2.t;//這個東西是優先隊列的優先級判斷功能 
 12     }
 13     int x;
 14     int y;
 15     int t;
 16     struct Node *prev;//指向前綴 
 17 };
 18 Node N[10003],P;
 19 bool success;
 20 int w;
 21 int dir[][2]={{1,0},{0,1},{-1,0},{0,-1}};
 22 char map[101][101];
 23 int mark[101][101],n,m;//hash函數和地圖大小 
 24 int _x[1001],_y[1001];//用來保存路徑 
 25 int main()
 26 {
 27     void bfs();
 28     while(scanf("%d%d",&n,&m)!=EOF)
 29     {
 30         int i;
 31         for(i=0;i<n;i++)
 32           cin>>map[i];
 33         success=false;
 34         bfs();//廣搜部分 
 35         if(success)
 36         {
 37           printf("It takes %d seconds to reach the target position, let me show you the way.\n",N[w].t);
 38           int len=N[w].t;
 39           _x[len]=N[w].x;_y[len]=N[w].y;
 40           Node *p;
 41           p=&N[w];
 42           int b=len;
 43           while(1)
 44           {
 45               p=p->prev;
 46               if(p==NULL)
 47                   break;
 48               b--;
 49               _x[b]=(*p).x;
 50             
 51               _y[b]=(*p).y;
 52             
 53           }
 54           int o=1;
 55       
 56           for(i=b;i<=len-1;i++)
 57           {
 58             
 59               if(map[_x[b+1]][_y[b+1]]=='.')
 60               {
 61                   printf("%ds:(%d,%d)->(%d,%d)\n",o,_x[b],_y[b],_x[b+1],_y[b+1]);
 62                   b++;
 63                   o++;
 64               }
 65               else if(map[_x[b+1]][_y[b+1]]!='.')
 66               {
 67                     printf("%ds:(%d,%d)->(%d,%d)\n",o,_x[b],_y[b],_x[b+1],_y[b+1]);
 68                     int v=o;
 69                     for( o=o+1; o<v+1+map[_x[b+1]][_y[b+1]]-'0';o++)
 70                     {
 71                         printf("%ds:FIGHT AT (%d,%d)\n",o,_x[b+1],_y[b+1]);
 72                     }
 73                     b++;
 74               }
 75             
 76           }
 77         
 78         }
 79         else
 80             printf("God please help our poor hero.\n");
 81         printf("FINISH\n");
 82     }
 83 }
 84 
 85 void bfs()
 86 {
 87   memset(mark,0,sizeof(mark));
 88   priority_queue<Node>Q;//這個是優先隊列定義 
 89   N[1].t=0;N[1].x=0;N[1].y=0;N[1].prev=NULL;
 90   mark[0][0]=1;
 91   Q.push(N[1]);
 92   w=2;
 93   while(!Q.empty())
 94   {
 95     
 96       N[w]=Q.top();//這個是一個很大的區別，如果普通隊列是front而優先則是輸出最優先的 
 97       Q.pop();
 98       if(N[w].x==n-1&&N[w].y==m-1)
 99       {
100           success=1;
101           break;//由于是優先隊列，所以第一次找到就成功了 
102       }
103       for(int i=0;i<4;i++)
104       {
105           int tx=N[w].x+dir[i][0];
106           int ty=N[w].y+dir[i][1];
107           if(tx>=0 && tx<n && ty>=0 && ty<m && !mark[tx][ty])
108           {
109             if(map[tx][ty]!='X')
110             {
111               P.x=tx;P.y=ty;P.prev=&N[w];
112               mark[tx][ty]=1;
113               if(map[tx][ty]=='.')
114               {
115                   P.t=N[w].t+1;
116                   Q.push(P);
117               }
118               if(map[tx][ty]!='.')
119               {
120                   P.t=N[w].t+1+map[tx][ty]-'0';
121                   Q.push(P);
122               }
123             }
124           }
125       }
126       w++;
127   }
128 
129 }//第一次用優先隊列，用的是論壇上的代碼，加了批注