首页 > 代码库 > HDU 1026 (BFS搜索+优先队列+记录方案)
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<<28struct 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[4][2]={-1,0,1,0,0,-1,0,1},map[105][105],spec[105][105],vis[105][105],ans;status path[105][105];void bfs(int x,int y){ priority_queue<status> Q; Q.push(status(x,y,map[x][y]-1)); vis[x][y]=true; bool flag=false; while(!Q.empty()) { if(flag) break; status t=Q.top();Q.pop(); for(int s=0;s<4;s++) { int X=t.x+dir[s][0],Y=t.y+dir[s][1]; if(vis[X][Y]||X<0||X>=n||Y<0||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==0&&Y==0) {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,0,sizeof(vis)); memset(spec,0,sizeof(spec)); ans=inf; for(int i=0; i<n; i++) { cin>>tt; for(int j=0; j<tt.size(); j++) { if(tt[j]==‘X‘) map[i][j]=0; else if(tt[j]==‘.‘) map[i][j]=1; else {map[i][j]=tt[j]-‘0‘+1;spec[i][j]=tt[j]-‘0‘;} } } bfs(n-1,m-1); 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=1,x=0,y=0; 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=1;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 |
HDU 1026 (BFS搜索+优先队列+记录方案)
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。