HDU1026 Ignatius and the Princess I（BFS+优先队列）
题目链接
题意：输入N*M大小的迷宫，’.'表示可以走，'X’表示不可以走，'n’表示扩展此结点需要n步，求解(0,0)到(N-1,M-1)的最短距离并输出路径
思路：迷宫问题的变式，扩展“怪物”结点的用时要加上怪物的HP，故可采用优先队列，优先扩展用时最少的结点。为了便于输出路径，先将终点入队，寻找终点到起点的路径，并把路径记录在一个pair类型的二维数组里（存储被扩展结点的父节点的坐标），这样BFS结束后就可以直接顺序输出路径了。
代码实现#include
#include
#include
#include
using namespace std;
int m,n;
char maze[110][110];
bool vis[110][110];
pair path[110][110];
int dis[][2]={{-1,0},{1,0},{0,-1},{0,1}};
struct s{
int x;
int y;
int t;
s(){}
s(int xx,int yy,int tt):x(xx),y(yy),t(tt){}
friend bool operator s2.t;
}
};
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
while(cin>>n>>m){
memset(vis,0,sizeof(vis));
memset(path,0,sizeof(path));
priority_queue q;
for(int i=0;i<n;i++){
for(int j=0;j>maze[i][j];
if(maze[i][j]=='X')
vis[i][j]=1;
}
}
q.push(s(n-1,m-1,0));
vis[n-1][m-1]=1;
bool flag=false;
while(!q.empty()){
s t=q.top();
if(t.x==0&&t.y==0){
flag=true;
break;
}
for(int i=0;i=0&&dy>=0&&dx<n&&dy='0'&&maze[n-1][m-1]<='9')
mint+=maze[n-1][m-1]-'0';
cout<<"It takes "<<mint<<" seconds to reach the target position, let me show you the way."<<endl;
int a,b,c,d,t;
a=b=0;t=1;
while(t<=mint){
c=path[a][b].first;d=path[a][b].second;
if(maze[a][b]=='.')
cout<<t++<<"s:("<<a<<","<<b<("<<c<<","<<d<<")"<<endl;
else{
int count=maze[a][b]-'0';
while(count--)
cout<<t++<<"s:FIGHT AT ("<<a<<","<<b<<")"<<endl;
if(t<mint)
cout<<t++<<"s:("<<a<<","<<b<("<<c<<","<<d<<")"<<endl;
}
a=c,b=d;
}
}
else{
cout<<"God please help our poor hero."<<endl;
}
cout<<"FINISH"<<endl;
}
return 0;
}
作者：Russellwzr
