广搜习惯了用队列，遇到一道输出路径的题就卡了。其实可以用数组来模拟队列，用DP的方法来求从终点到起点的最小值，这就是所谓的记忆化搜索：算法上依然是搜索的流程，但是搜索到的一些解用动态规划的那种思想和模式作一些保存。
别人的代码我就不贴原创了，支持正版。
#include <cstdio>
#include <queue>
#include <cstring>
using namespace std;
const int inf=1000000;
const int maxn=100+5;
int mi[maxn][maxn];
char g[maxn][maxn];
struct node
{
int x,y,t,p;
}f[inf];
int dir[4][2]={{-1,0},{0,-1},{0,1},{1,0}};
int k,n,m;
void BFS()
{
int I=0,J=1;
while(I!=J)
{
node R=f[I];
for(int i=0;i<4;i++)
{
node M=R;
M.x+=dir[i][0];
M.y+=dir[i][1];
if(M.x<0|| M.x>=n|| M.y<0|| M.y>=m|| g[M.x][M.y]=='X')continue;
M.t++;
if(g[M.x][M.y]!='.')
M.t+=g[M.x][M.y]-'0';
if(M.t<mi[M.x][M.y])
{
mi[M.x][M.y]=M.t;
M.p=I;
if(M.x==0&&M.y==0) k=J;
f[J++]=M;
}
}
I++;
}
}
int main()
{
while(~scanf("%d%d",&n,&m))
{
for(int i=0;i<n;i++)
{
scanf("%s",g[i]);
for(int j=0;j<m;j++)
mi[i][j]=inf;
}
f[0].x=n-1,f[0].y=m-1;
f[0].p=-1,f[0].t=0;
if(g[n-1][m-1]!='X'&&g[n-1][m-1]!='.')
f[0].t=g[n-1][m-1]-'0';
BFS();
if(mi[0][0]==inf)
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",mi[0][0]);
node R=f[k];
int t=1;
while(R.p>=0)
{
printf("%ds:(%d,%d)->(%d,%d)\n",t++, R.x, R.y, f[R.p].x, f[R.p].y);
if(g[f[R.p].x][f[R.p].y]!='X'&& g[f[R.p].x][f[R.p].y]!='.')
for(int i=0; i<g[f[R.p].x][f[R.p].y]-'0'; ++i)
printf("%ds:FIGHT AT (%d,%d)\n",t++,f[R.p].x, f[R.p].y);
R=f[R.p];
}
}
printf("FINISH\n");
}
return 0;
}