http://acm.hdu.edu.cn/showproblem.php?pid=1026
模拟一个人走迷宫,起点在(0,0)位置,遇到怪兽要和他决斗，决斗时间为那个格子的数字,就是走一个格子花费时间1,
遇到有数字的格子还要花费这个数字大小的时间,输出最后走到(n-1,m-1)的最小时间,还要输出他的路径，'X'是墙,‘.’是可以走的空地
就是这个路径,刚一看题看到那个样例输出吓得我都飞起来了,好多啊！
其实还好啦,广搜,一开始还因为是普通的广搜,后来发现不一样,
为了寻求最小时间,他可以选择走有数字的格子也可以选择绕过去,看哪个时间短一些
首先求出最小时间,跟那个连连看差不多,用visit数组初始化很大,来储存到达每个点的最小时间
然后输出路径的时候用递归回溯,因为广搜是广泛的搜索,并不能保证走过的点都是最短路径上的点
所以从终点开始利用他的方向来往前回溯,注意因为没有用优先队列和输出漏了句号所以刚开始wa了几发
code
#include<cstdio>
#include<climits>
#include<queue>
#include<cstring>
using namespace std;
char map[][];
int visit[][];
int flag[][];
struct point{
int x,y;
int time;
friend bool operator<(point n1,point n2)
{
return n2.time<n1.time;
}
};
int n,m,t;
int dx[]={,,,-};
int dy[]={,-,,};
int bfs()
{
int i;
priority_queue<point>Q;
point now,next;
now.x=;now.y=;
now.time=;
visit[][]=;
Q.push(now);
while (!Q.empty())
{
now=Q.top();
Q.pop();
if (now.x==n-&&now.y==m-)
return visit[now.x][now.y];
for (i=;i<;i++)
{
next.x=now.x+dx[i];
next.y=now.y+dy[i];
if (next.x<||next.x>=n||next.y<||next.y>=m)continue;
if (map[next.x][next.y]=='X')continue;
if (map[next.x][next.y]=='.')
next.time=now.time+;
else
next.time=now.time++(map[next.x][next.y]-'');
if (map[next.x][next.y]<=''&&map[next.x][next.y]>=''&&visit[next.x][next.y]>now.time+(map[next.x][next.y]-''))
{
visit[next.x][next.y]=now.time++(map[next.x][next.y]-'');
flag[next.x][next.y]=i+;
Q.push(next);
}
else if (map[next.x][next.y]=='.'&&visit[next.x][next.y]>now.time+)
{
visit[next.x][next.y]=now.time+;
flag[next.x][next.y]=i+;
Q.push(next);
}
}
}
return -;
}
void output(int x,int y)//回溯
{
int sx,sy;
if (flag[x][y]==) return ;
sx=x-dx[flag[x][y]-];
sy=y-dy[flag[x][y]-];
output(sx,sy);
printf("%ds:(%d,%d)->(%d,%d)\n",t++,sx,sy,x,y);
if (map[x][y]<=''&&map[x][y]>='')
{
int w=map[x][y]-'';
while (w--)
printf("%ds:FIGHT AT (%d,%d)\n",t++,x,y);
}
}
int main()
{
int i,j,q;
while (~scanf("%d %d",&n,&m))
{
getchar();
for (i=;i<n;i++)
{
for (j=;j<m;j++)
scanf(" %c",&map[i][j]);
}
for (i=;i<n;i++)
for (j=;j<m;j++)
{
visit[i][j]=INT_MAX;
flag[i][j]=;
}
q=bfs();
if (q==-)
{
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",q);
t=;
output(n-,m-);
puts("FINISH");
}
}
return ;
}