学步园

本来一道简单的搜索题，输出方式是难点

#include<stdio.h>
#include<string.h>
#include<queue>
#define inf 0x3fffffff
using namespace std;
int m,n,dp[510][510],dr[510][510];//记录到达该点的方向
char map[510][510];
int dir[4][2]={0,1,1,0,0,-1,-1,0};
int judge(int x,int y)
{
	if(x>=0&&x<n&&y>=0&&y<m&&map[x][y]!='X')
		return 1;
	return 0;
}
struct op
{
	int x,y,step,k;
};
void bfs()
{
	queue<op>Q;
	int i,k,x,y;
	op cur,next;
	cur.x=0;
	cur.y=0;
	cur.step=0;
	cur.k=-1;
	dp[0][0]=0;
	Q.push(cur);
	while(!Q.empty())
	{
		cur=Q.front();
		Q.pop();
		for(i=0;i<4;i++)
		{
			x=next.x=cur.x+dir[i][0];
			y=next.y=cur.y+dir[i][1];
			next.step=cur.step+1;
			k=next.k=i;
			if(judge(x,y)==0)continue;
			if(map[x][y]>='1'&&map[x][y]<='9')
				next.step+=(map[x][y]-'0');
			if(dp[x][y]>next.step)
			{Q.push(next);dp[x][y]=next.step;dr[x][y]=k;}
		}
	}
}
void prin(int x,int y,int t)
{
	if(t<=0)return ;//栈溢出，找了半天试着加上这句就AC了，现在还不明白为什么？？
	int k=0;
	if(t==1)
	{
		printf("%ds:(%d,%d)->(%d,%d)\n",t,x-dir[dr[x][y]][0],y-dir[dr[x][y]][1],x,y);
	     return ;
	}
	else 
	{
		if(map[x][y]>='1'&&map[x][y]<='9')
		{
			k=map[x][y]-'0';
			prin(x-dir[dr[x][y]][0],y-dir[dr[x][y]][1],t-k-1);
				printf("%ds:(%d,%d)->(%d,%d)\n",t-k,x-dir[dr[x][y]][0],y-dir[dr[x][y]][1],x,y);
			for(int j=k-1;j>=0;j--)
				printf("%ds:FIGHT AT (%d,%d)\n",t-j,x,y);			
		}
		else
		{
			prin(x-dir[dr[x][y]][0],y-dir[dr[x][y]][1],t-1);
		   printf("%ds:(%d,%d)->(%d,%d)\n",t,x-dir[dr[x][y]][0],y-dir[dr[x][y]][1],x,y);
		}
	}
}
int main()
{
	int i,j,k;
	while(scanf("%d%d",&n,&m)!=-1)
	{
		memset(dr,-1,sizeof(dr));
		for(i=0;i<n;i++)
			for(j=0;j<m;j++)
				dp[i][j]=inf;//到达该点的最小时间
		for(i=0;i<n;i++)
			scanf("%s",map[i]);
	    bfs();
		if(dp[n-1][m-1]==inf)
		{
			puts("God please help our poor hero.");
            puts("FINISH");
		}
		else 
		{
			printf("It takes %d seconds to reach the target position, let me show you the way.\n",dp[n-1][m-1]);
			prin(n-1,m-1,dp[n-1][m-1]);
			puts("FINISH");
		}
	}
	return 0;
}