先用BFS，把到每个点需要的时间纪录下来，然后从终点开始，用递归找路径到起点，然后利用递归一个一个输出来，这道题刚看到的时候想自己做，然后发现自己的考虑有误，它不是单纯的求时间，还要一步一步输出来，用BFS肯定没法输出来，当把每个时间纪录下来后，发现用DFS也没法输出来，然后从网上看到用递归，从最后一个点，用判断相等的方式，递归到起点后开始输出。
#include <iostream>
#include <stdio.h>
#include <queue>
using namespace std;
int dir[4][2]={1,0,0,1,-1,0,0,-1};
int flag[110][110],n,m,result;
char map[110][110];
int check(int x,int y)
{
if(x>=0&&x<n&&y>=0&&y<m)
return 1;
return 0;
}
struct point
{
int x,y,time;
};
int bfs(int sx,int sy)
{
queue<point> Q;
point e,t;
e.x=sx;
e.y=sy;
e.time=0;
Q.push(e);
flag[sx][sy]=0;
while(!Q.empty())
{
e=Q.front();
if(e.x==n-1&&e.y==m-1)
{
if(e.time<result)
result=e.time;
}
Q.pop();
for(int i=0;i<4;i++)
{
int xx=e.x+dir[i][0];
int yy=e.y+dir[i][1];
if(check(xx,yy)==0)
continue;
if(map[xx][yy]=='X')
continue;
if(map[xx][yy]>='1'&&map[xx][yy]<='9')
{
t.x=xx;
t.y=yy;
t.time=e.time+map[xx][yy]-'0'+1;
if(t.time< flag[xx][yy]&&t.time<=result)
{
flag[xx][yy]=t.time;
Q.push(t);
}
}
else if(map[xx][yy]=='.')
{
t.x=xx;
t.y=yy;
t.time=e.time+1;
if(t.time< flag[xx][yy]&&t.time<=result)
{
flag[xx][yy]=t.time;
Q.push(t);
}
}
}
}
return result;
}
void print(int x,int y,int step)
{
if(step==0)
return;
int time=0,t;
int dx,dy,rx,ry;
if(map[x][y]>='1'&&map[x][y]<='9')
time=map[x][y]-'0';
for(int i=0;i<4;i++)
{
dx=x+dir[i][0];
dy=y+dir[i][1];
if(check(dx,dy)==1)
{
int t=0;
if(map[x][y]>='1'&&map[x][y]<='9')
t=map[x][y]-'0';
if(flag[dx][dy]+1+t==flag[x][y])
{
rx=dx;
ry=dy;
print(dx,dy,step-time-1);
break;
}
}
}
printf("%ds:(%d,%d)->(%d,%d)\n",step-time,rx,ry,x,y);
while(time>0)
{
printf("%ds:FIGHT AT (%d,%d)\n",step-time+1,x,y);
time--;
}
return;
}
int main()
{
while(scanf("%d %d\n",&n,&m)!=EOF)
{
for(int i=0;i<n;i++)
scanf("%s",map[i]);
result=1000000;
for(int i=0;i<n;i++)
{
for(int j=0;j<m;j++)
flag[i][j]=1000000;
}
int end=bfs(0,0);
if(end==1000000)
printf("God please help our poor hero.\n");
else
{
printf("It takes %d seconds to reach the target position, let me show you the way.\n",end);
print(n-1,m-1,end);
}
printf("FINISH\n");
}
return 0;
}
