1 #include<iostream>
  2 #include<queue>
  3 #include<algorithm>
  4 #include<stack>
  5 using namespace std;
  6 #define MAXSIZE 100
  7 struct node{
  8     int x,y,ti;
  9     node(int _x=0,int _y=0,int _ti=0):x(_x),y(_y),ti(_ti){};
 10     friend bool operator <(const node &a, const node &b){
 11         return a.ti>b.ti;
 12     }
 13 };
 14 node f[MAXSIZE][MAXSIZE];
 15 char map[MAXSIZE][MAXSIZE];
 16 bool visited[MAXSIZE][MAXSIZE];
 17 bool getIt;
 18 int n,m,mins;
 19 int dir[4][2]={
 20     {1,0},
 21     {-1,0},
 22     {0,1},
 23     {0,-1}
 24 };
 25 
 26 void bfs(){
 27     node t,b;
 28     t.x=0;t.y=0;t.ti=0;
 29     priority_queue<node> Q;
 30     Q.push(t);
 31     visited[0][0]=true;
 32     while(!Q.empty()){
 33         b=Q.top();
 34         Q.pop();
 35         if(b.x==n-1&&b.y==m-1){
 36             getIt=true;
 37             mins=b.ti;
 38             return;
 39         }
 40         for(int k=0;k<4;k++){
 41             int i=b.x+dir[k][0];
 42             int j=b.y+dir[k][1];
 43             if(i<0||i>=n||j<0||j>=m)
 44                 continue;
 45             if(!visited[i][j]&&map[i][j]!='X'){
 46                 visited[i][j]=true;
 47                 f[i][j].x=b.x;f[i][j].y=b.y;f[i][j].ti=b.ti+1;//記錄前驅
 48                 if(map[i][j]=='.')
 49                     Q.push(node(i,j,b.ti+1));
 50                 else 
 51                     Q.push(node(i,j,b.ti+(map[i][j]-'0')+1));
 52             }
 53         }
 54     }
 55     puts("God please help our poor hero.");
 56 }
 57 inline void print(){
 58     stack<node> S;
 59     node temp=f[n-1][m-1];//終點的第一前繼點
 60     S.push(node(n-1,m-1,mins));//將終點放入
 61     while(temp.x!=0||temp.y!=0){//未到起點時
 62         S.push(temp);
 63         temp=f[temp.x][temp.y];
 64     }
 65     int k,t=1;
 66     if(map[0][0]!='.'){
 67         k=map[0][0]-'0';
 68         while(k--)
 69             printf("%ds:FIGHT AT (%d,%d)\n",t++,0,0);
 70     }
 71     while(!S.empty()){
 72         temp=S.top();
 73         S.pop();
 74         if(map[temp.x][temp.y]=='.')
 75             printf("%ds:(%d,%d)->(%d,%d)\n",t++,f[temp.x][temp.y].x,f[temp.x][temp.y].y,temp.x,temp.y);
 76         else {
 77             printf("%ds:(%d,%d)->(%d,%d)\n",t++,f[temp.x][temp.y].x,f[temp.x][temp.y].y,temp.x,temp.y);
 78             k=map[temp.x][temp.y]-'0';
 79             while(k--)
 80                 printf("%ds:FIGHT AT (%d,%d)\n",t++,temp.x,temp.y);
 81         }
 82     }
 83 }
 84 inline void scan(char &ch){
 85     while(ch=getchar())
 86         if(ch=='.'||ch=='X'||(ch>='1'&&ch<='9'))
 87             return ;
 88 }
 89 int main(){
 90     //freopen("in.txt","r",stdin);
 91     while(scanf("%d%d",&n,&m)!=EOF){
 92         for(int i=0;i<n;i++){
 93             for(int j=0;j<m;j++)
 94                 scan(map[i][j]);
 95         }
 96         if(map[0][0]=='X'||map[n-1][m-1]=='X'){
 97             puts("God please help our poor hero.");
 98             continue;
 99         }
100         memset(visited,false,sizeof(visited));
101         getIt=false;
102         bfs();
103         if(getIt){
104             printf("It takes %d seconds to reach the target position, let me show you the way.\n",mins);
105             print();
106         } 
107         puts("FINISH");
108     }
109     return 0;
110 }