题目源地址：http://acm.hdu.edu.cn/showproblem.php?pid=1026
//HOJ--1026:Ignatius and the Princess I
#include<iostream>
#include<memory.h>
#include<stdio.h>
#include<queue>
using namespace std;
struct Coordinate
{
int x,y;
int step;
//因为存在怪兽而在原地打死怪兽也需要时间，若不使用优先队列则可能两条路径上下左右走过的路径一样长，
//而打怪兽的时间不一样，使用优先队列保证了时间的最短
friend bool operator<(Coordinate c1,Coordinate c2)
{
return c2.step<c1.step;
}
}start,next,temp;
struct path //存储路径
{
int x,y;
int time;
}path[110][110];
char map[110][110];
int visited[110][110];
int N,M;
int dx[]={-1,1,0,0};
int dy[]={0,0,-1,1};
int BFS()
{
priority_queue <Coordinate> Q;
Q.push(start);
visited[start.x][start.y]=1;
while(!Q.empty())
{
temp=Q.top();
Q.pop();
if(temp.x==N-1 && temp.y==M-1)
return temp.step;
for(int i=0;i<4;i++)
{
next.x=temp.x+dx[i];
next.y=temp.y+dy[i];
if(next.x>=0 && next.x<N && next.y>=0 && next.y<M && !visited[next.x][next.y] && map[next.x][next.y]!='X')
{
visited[next.x][next.y]=1;
if(map[next.x][next.y]=='.')
{
next.step=temp.step+1;
Q.push(next);
visited[next.x][next.y]=1;
path[next.x][next.y].x=temp.x; //记录路径,前驱节点
path[next.x][next.y].y=temp.y;
path[next.x][next.y].time=1;
}
else
{
next.step=temp.step+1+(map[next.x][next.y]-'0');
Q.push(next);
visited[next.x][next.y]=1;
path[next.x][next.y].x=temp.x; //记录路径,前驱节点
path[next.x][next.y].y=temp.y;
path[next.x][next.y].time=map[next.x][next.y]-'0'+1;
}
}
}
}
return 0;
}
void OutputPath(int t,int px,int py)//递归输出路径
{
if(t==1) cout<<t<<"s:("<<path[px][py].x<<","<<path[px][py].y<<")->("<<px<<","<<py<<")"<<endl;
else if(path[px][py].time==1)
{
OutputPath(t-1,path[px][py].x,path[px][py].y);
cout<<t<<"s:("<<path[px][py].x<<","<<path[px][py].y<<")->("
<<px<<","<<py<<")"<<endl;
}
else
{
--path[px][py].time;
OutputPath(t-1,px,py);
cout<<t<<"s:FIGHT AT ("<<px<<","<<py<<")"<<endl;
}
}
int main()
{
int i,j;
int ans;
while(cin>>N>>M)
{
getchar();
memset(visited,0,sizeof(visited));
for(i=0;i<N;i++)
for(j=0;j<M;j++)
cin>>map[i][j];
start.x=0;
start.y=0;
start.step=0;
path[0][0].x=-1; //起始点无前驱节点
path[0][0].y=-1;
path[0][0].time=0;
ans=BFS();
if(ans)
{
cout<<"It takes "<<ans<<" seconds to reach the target position, let me show you the way."<<endl;
OutputPath(ans,N-1,M-1);
}
else
cout<<"God please help our poor hero."<<endl;
cout<<"FINISH"<<endl;
}
//system("pause");
return 0;
}
版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 举报，一经查实，本站将立刻删除。
文章由极客之音整理，本文链接：https://www.bmabk.com/index.php/post/163061.html
