1 #include<cstdio>
 2 #include<cstring>
 3 #include<queue>
 4 #include<string>
 5 using namespace std;
 6 struct que
 7 {
 8     int x,y,s;
 9     string p;
10     friend bool operator<(const que & a,const que & b)
11     {
12         return a.s > b.s;
13     }
14 }frt,tmp;
15 priority_queue<que>Q;
16 const int dx[]={-1, 0,+1, 0};
17 const int dy[]={ 0,+1, 0,-1};
18 int n,m;
19 char ma[111][111];
20 char ch[20];
21 void prt(que q)
22 {
23     printf("It takes %d seconds to reach the target position, let me show you the way.\n",q.s);
24     int len=q.p.length(),i,j=0,k,t=0;
25     que pre,now;
26     pre.x=pre.y=pre.s=0;
27     for(i=0;i<len;i++)
28     if(q.p[i]==‘-‘)
29     {
30         for(k=0;j<i;j++)ch[k++]=q.p[j];
31         ch[k]=‘\0‘;
32         sscanf(ch,"%d,%d,%d",&now.x,&now.y,&now.s);
33         printf("%ds:(%d,%d)->(%d,%d)\n",++t,pre.x,pre.y,now.x,now.y);
34         for(k=now.s-pre.s;k>1;k--)printf("%ds:FIGHT AT (%d,%d)\n",++t,now.x,now.y);
35         pre=now;
36         i=j++;
37     }
38     //printf("%s\n",q.p.c_str());
39     puts("FINISH");
40 }
41 void bfs()
42 {
43     while(!Q.empty())Q.pop();
44     tmp.x=tmp.y=tmp.s=0;
45     tmp.p="";
46     Q.push(tmp);
47     ma[0][0]=‘X‘;
48     int i;
49     while(!Q.empty())
50     {
51         frt=Q.top();
52         if(frt.x==n-1&&frt.y==m-1)
53         {
54             prt(frt);
55             return;
56         }
57         Q.pop();
58         for(i=0;i<4;i++)
59         {
60             tmp.x=frt.x+dx[i];
61             tmp.y=frt.y+dy[i];
62             if(0<=tmp.x&&tmp.x<n&&0<=tmp.y&&tmp.y<m&&ma[tmp.x][tmp.y]!=‘X‘)
63             {
64                 tmp.s=frt.s+1;
65                 if(ma[tmp.x][tmp.y]!=‘.‘)tmp.s+=(ma[tmp.x][tmp.y]-‘0‘);
66                 sprintf(ch,"%d,%d,%d-",tmp.x,tmp.y,tmp.s);
67                 tmp.p=frt.p+string(ch);
68                 Q.push(tmp);
69                 ma[tmp.x][tmp.y]=‘X‘;
70             }
71         }
72     }
73     printf("God please help our poor hero.\nFINISH\n");
74 }
75 int main()
76 {
77     int i;
78     while(scanf("%d%d",&n,&m)!=EOF)
79     {
80         for(i=0;i<n;i++)scanf("%s",ma[i]);
81         bfs();
82     }
83     return 0;
84 }