本來一道簡單的搜索題，輸出方式是難點
[cpp] #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;
}
