HDU1026(延时迷宫:BFS+优先队列)
Ignatius and the Princess I
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Others)
Total Submission(s): 16713 Accepted Submission(s): 5327
Special Judge
1.Ignatius can only move in four directions(up, down, left, right), one step per second. A step is defined as follow: if current position is (x,y), after a step, Ignatius can only stand on (x-1,y), (x+1,y), (x,y-1) or (x,y+1).
2.The array is marked with some characters and numbers. We define them like this:
. : The place where Ignatius can walk on.
X : The place is a trap, Ignatius should not walk on it.
n : Here is a monster with n HP(1<=n<=9), if Ignatius walk on it, it takes him n seconds to kill the monster.
Your task is to give out the path which costs minimum seconds for Ignatius to reach target position. You may assume that the start position and the target position will never be a trap, and there will never be a monster at the start position.
#include <iostream>
#include <queue>
using namespace std;
const int MAXN=;
const int INF=0x3f3f3f3f;
struct Node{
int y,x,hp,step,id,pre;
Node(){}
Node(int y,int x,int hp,int step,int id,int pre)
{
this->y=y;
this->x=x;
this->hp=hp;
this->step=step;
this->id=id;
this->pre=pre;
}
bool operator<(const Node& no)const
{
return step > no.step;
}
}path[];
int tot;
int n,m;
int t[MAXN][MAXN];
char mz[MAXN][MAXN];
int dy[]={,,,-};
int dx[]={,,-,};
int start;
int time;
void print(int k)
{
Node now=path[k];
if(now.pre==-)
{
++time;
cout<<time<<"s:("<<now.y<<","<<now.x<<")->";
return ;
}
print(now.pre);
cout<<"("<<now.y<<","<<now.x<<")"<<endl;
for(int i=;i<now.hp;i++)
{
++time;
cout<<time<<"s:FIGHT AT ("<<now.y<<","<<now.x<<")"<<endl;
}
time++;
if(k!=start) cout<<time<<"s:("<<now.y<<","<<now.x<<")->";
}
void bfs()
{
tot=;
for(int i=;i<MAXN;i++)
for(int j=;j<MAXN;j++)
t[i][j]=INF;
priority_queue<Node> que;
Node now(,,,,tot,-);
path[tot++]=now;
que.push(now);
t[][]=;
while(!que.empty())
{
now=que.top();que.pop();
if(now.y==n-&&now.x==m-)
{
start=now.id;
cout<<"It takes "<<path[start].step<<" seconds to reach the target position, let me show you the way."<<endl;
time=;
print(start);
return ;
}
for(int i=;i<;i++)
{
int ny=now.y+dy[i];
int nx=now.x+dx[i];
if(<=ny&&ny<n&&<=nx&&nx<m&&mz[ny][nx]!='X')
{
int hp=;
if(mz[ny][nx]!='.') hp=hp+mz[ny][nx]-'';
int nstep=now.step+hp+;
if(nstep<t[ny][nx])
{
t[ny][nx]=nstep;
Node next=Node(ny,nx,hp,nstep,tot,now.id);
que.push(next);
path[tot++]=next;
}
}
}
}
cout<<"God please help our poor hero."<<endl;
}
int main()
{
while(cin>>n>>m)
{
for(int i=;i<n;i++)
cin>>mz[i];
bfs();
cout<<"FINISH"<<endl;
}
return ;
}
最新文章
- mysql易混淆知识点
- Mac技巧
- Asp.Net学习进度备忘(第一步:ASP.NET Web Forms)
- jquery 显示“加载状态 结束”
- python(6)
- Qt学习之路(54): 自定义拖放数据对象
- 微信第三方登录(原生)demo
- CentOS配置防火墙操作实例
- 大一上c语言学习总结
- 将含有makefile文件的源码加入Eclipse工程
- 单反毁三代,kindle富一生
- windows下git的使用
- unigui1404在delphi10.2.2安装
- Linux-文件查找命令find
- 数据同步canal服务端HA配置
- Luogu 1613 跑路(最短路径,倍增)
- 移动端H5地图离线瓦片方案(1)(2)
- Mac下更新SVN
- linux 安全狗安装问题
- 错误结果保存示例 - 【jmeter】