HDU 1026 (BFS搜索+优先队列+记录方案)

题目链接http://acm.hdu.edu.cn/showproblem.php?pid=1026

题目大意:最短时间内出迷宫。迷宫里要杀怪,每个怪有一定HP,也就是说要耗一定时。输出方案。

解题思路

要是没有输出方案,就是一个简单粗暴的BFS。

一开始解决输出方案问题时,简单粗暴地在每次状态里加个vector,然后连带vector一起转移。

结果vector的push_back实在太慢,无论怎么优化都是T。

于是参考了ACMan同学的方案,path[X][Y]记录下父亲点。

最后输出的时候,要么递归输出,要么就选择从终点BFS, 这样就可以顺序输出。

#include "cstdio"
#include "cstring"
#include "string"
#include "iostream"
#include "queue"
#include "vector"
using namespace std;
#define inf 1<<28
struct status
{
int x,y,dep;
status() {}
status(int x,int y,int dep):x(x),y(y),dep(dep) {}
bool operator < (const status &a) const
{
return dep > a.dep;
}
};
int n,m,dir[][]={-,,,,,-,,},map[][],spec[][],vis[][],ans;
status path[][];
void bfs(int x,int y)
{
priority_queue<status> Q;
Q.push(status(x,y,map[x][y]-));
vis[x][y]=true;
bool flag=false;
while(!Q.empty())
{
if(flag) break;
status t=Q.top();Q.pop();
for(int s=;s<;s++)
{
int X=t.x+dir[s][],Y=t.y+dir[s][];
if(vis[X][Y]||X<||X>=n||Y<||Y>=m||!map[X][Y]) continue;
vis[X][Y]=true;
path[X][Y].x=t.x;
path[X][Y].y=t.y;
Q.push(status(X,Y,t.dep+map[X][Y]));
if(X==&&Y==) {flag=true;ans=min(ans,t.dep+map[X][Y]);break;}
}
}
}
int main()
{
ios::sync_with_stdio(false);
string tt;
while(cin>>n>>m)
{
memset(vis,,sizeof(vis));
memset(spec,,sizeof(spec));
ans=inf;
for(int i=; i<n; i++)
{
cin>>tt;
for(int j=; j<tt.size(); j++)
{
if(tt[j]=='X') map[i][j]=;
else if(tt[j]=='.') map[i][j]=;
else {map[i][j]=tt[j]-''+;spec[i][j]=tt[j]-'';}
}
}
bfs(n-,m-);
if(ans==inf) printf("God please help our poor hero.\n");
else
{
printf("It takes %d seconds to reach the target position, let me show you the way.\n",ans);
int no=,x=,y=;
while(no<=ans)
{
int fx=path[x][y].x,fy=path[x][y].y;
if(map[fx][fy]) printf("%ds:(%d,%d)->(%d,%d)\n",no++,x,y,fx,fy);
for(int i=;i<=spec[fx][fy];i++) printf("%ds:FIGHT AT (%d,%d)\n",no++,fx,fy);
x=fx,y=fy;
}
}
printf("FINISH\n");
}
}
11872162 2014-10-14 19:47:07 Accepted 1026 15MS 552K 2286 B C++ Physcal
上一篇:Zeppelin 用jdbc连接hive报错


下一篇:Python黑帽编程 2.0 第二章概述