首页 > 代码库 > HDU 2653 (记忆化BFS搜索+优先队列)
HDU 2653 (记忆化BFS搜索+优先队列)
题目链接: http://acm.hdu.edu.cn/showproblem.php?pid=2653
题目大意：迷宫中有普通点和陷阱。其中普通点可以走可以飞，但是陷阱只能飞。走耗时1，飞耗时2。但是飞耗能1。给定一定能量P，问是否能在T秒内走出。
解题思路：
一开始SB似地认为每个点最多访问两次。其实每个点最多可以访问P次。
vis[X][Y][P]表示在(x,y)点能量为P的状态。
容易出错的地方在于这个组合: @. ,虽说是飞吧，但是还是会在陷阱上卡1s，尽管下一个点是. ,但是这种情况是必须飞的。
@@肯定是飞的，..这个就是可飞，可不飞。
BFS树明显是不均衡的，使用优先队列找到的第一个答案就可以return。
#include "cstdio"#include "string"#include "cstring"#include "iostream"#include "queue"using namespace std;char map[85][85];int n,m,T,p,no,sx,sy,ex,ey,vis[85][85][85],dir[4][2]={-1,0,1,0,0,-1,0,1};struct status{ int x,y,dep,mana; status(int x,int y,int dep,int mana):x(x),y(y),dep(dep),mana(mana) {} bool operator < (const status &a) const {return dep > a.dep;}};int bfs(int x,int y,int mana){ priority_queue<status> Q; Q.push(status(x,y,0,mana)); vis[x][y][mana]=1; while(!Q.empty()) { status t=Q.top();Q.pop(); if(t.dep>=T) return -1; for(int s=0;s<4;s++) { int X=t.x+dir[s][0],Y=t.y+dir[s][1]; if(X<1||X>n||Y<1||Y>m||map[X][Y]==‘#‘) continue; if(map[X][Y]==‘@‘) { if(t.mana<1||vis[X][Y][t.mana-1]) continue; vis[X][Y][t.mana-1]=true; Q.push(status(X,Y,t.dep+1,t.mana-1)); } else { if(map[t.x][t.y]==‘@‘&&t.mana<1) continue; if(X==ex&&Y==ey) { if(t.mana>=1) return t.dep+1; else return t.dep+2; } if(t.mana>=1||map[t.x][t.y]==‘@‘) { if(!vis[X][Y][t.mana-1]) {vis[X][Y][t.mana-1]=true;Q.push(status(X,Y,t.dep+1,t.mana-1));} } if(map[t.x][t.y]!=‘@‘&&!vis[X][Y][t.mana]) {vis[X][Y][t.mana]=true;Q.push(status(X,Y,t.dep+2,t.mana));} } } } return -1;}int main(){ //freopen("in.txt","r",stdin); ios::sync_with_stdio(false); string tt; while(cin>>n>>m>>T>>p) { memset(vis,0,sizeof(vis)); for(int i=1;i<=n;i++) { cin>>tt; for(int j=0;j<tt.size();j++) { map[i][j+1]=tt[j]; if(tt[j]==‘Y‘) {sx=i;sy=j+1;} if(tt[j]==‘L‘) {ex=i;ey=j+1;} } } int ans=bfs(sx,sy,p); cout<<"Case "<<++no<<":"<<endl; if(ans>T||ans==-1) cout<<"Poor Yifenfei, he has to wait another ten thousand years."<<endl; else cout<<"Yes, Yifenfei will kill Lemon at "<<ans<<" sec."<<endl; }}
| 11892623 | 2014-10-17 12:22:29 | Accepted | 2653 | 218MS | 2956K | 2378 B | C++ | Physcal |
HDU 2653 (记忆化BFS搜索+优先队列)
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。