题意:从0,0点出发到n-1,m-1点,路上的数字代表要在这个点额外待多少秒,求最短的路
递归输出路径即可
#include<cstdio>
#include<iostream>
#include<algorithm>
#include<cstring>
#include<cmath>
#include<queue>
#include<map>
using namespace std;
#define MOD 1000000007
const int INF=0x3f3f3f3f;
const double eps=1e-;
#define cl(a) memset(a,0,sizeof(a))
#define ts printf("*****\n");
const int MAXN=;
int n,m,tt;
int sumt=;
struct node
{
int x,y,t;
node(){}
node(int xx,int yy,int tt)
{
x=xx,y=yy,t=tt;
}
friend bool operator<(node a,node b)
{
return a.t>b.t;
}
};
bool vis[MAXN][MAXN];
int dir[MAXN][MAXN];
char maze[MAXN][MAXN];
int d[][]={,,,,-,,,-};
int kk=;
int outpath(int x,int y) //递归输出,从x,y出发所在的时间
{
if(x==&&y==)
{
int nt=;
printf("%ds:(%d,%d)->",nt,x,y);
return nt;
}
else
kk=dir[x][y];
int nt=outpath(x-d[kk][],y-d[kk][]);
printf("(%d,%d)\n",x,y);
if(<maze[x][y]-''&&maze[x][y]-''<=)
{
int l=maze[x][y]-'';
while(l--)
printf("%ds:FIGHT AT (%d,%d)\n",++nt,x,y);
}
if(nt==sumt) return ;
printf("%ds:(%d,%d)->",++nt,x,y);
return nt;
}
void bfs()
{
node now,next;
priority_queue<node> q;
q.push(node(,,));
vis[][]=;
while(!q.empty())
{
now=q.top();
q.pop();
if(now.x==n-&&now.y==m-)
{
printf("It takes %d seconds to reach the target position, let me show you the way.\n",now.t);
sumt=now.t;
outpath(n-,m-);
printf("FINISH\n");
return;
}
for(int i=;i<;i++)
{
next.x=now.x+d[i][];
next.y=now.y+d[i][];
next.t=now.t+;
if(next.x>=&&next.y>=&&next.x<n&&next.y<m&&!vis[next.x][next.y]&&maze[next.x][next.y]!='X')
{
if(''<maze[next.x][next.y]&&maze[next.x][next.y]<='')
{
next.t+=maze[next.x][next.y]-'';
vis[next.x][next.y]=;
dir[next.x][next.y]=i;
q.push(next);
}
else
{
dir[next.x][next.y]=i;
vis[next.x][next.y]=;
q.push(next);
}
}
}
}
puts("God please help our poor hero.\nFINISH");
}
int main()
{
int i,j,k;
#ifndef ONLINE_JUDGE
freopen("1.in","r",stdin);
#endif
while(scanf("%d%d",&n,&m)!=EOF)
{
for(i=;i<n;i++)
{
scanf("%s",maze[i]);
}
cl(vis);
bfs();
}
}