首页 > 代码库 > HDU 1429 (BFS+记忆化状压搜索)
HDU 1429 (BFS+记忆化状压搜索)
题目链接: http://acm.hdu.edu.cn/showproblem.php?pid=1429
题目大意：最短时间内出迷宫，可以走回头路，迷宫内有不同的门，对应不同的钥匙。
解题思路：
要是没有门和钥匙，而且不能走回头路，就是个简单粗暴的BFS。
有了门之后，就要状态压缩+记忆化搜索。不然这个图会搜死你。
本题的状态压缩基于一个事实：尽管可以走回头路，但是回头是有理由的，你要么开了门，要么拿了钥匙，使状态发生改变。
否则等于多绕了一步，浪费时间，应该及时剪枝。
f[x][y][key]保存的是在(x,y)点，手里钥匙是key(位压缩)的状态。
那么对于门，key&(1<<k)检测当前是否有该门的钥匙。
对于钥匙，key|(1<<k)获得钥匙。
每次push之前，记录一下f[x][y][key]就行了
#include "cstdio"#include "cstring"#include "string"#include "iostream"#include "queue"using namespace std;int n,m,t,sx,sy,ex,ey,f[25][25][1200],dir[4][2]={-1,0,1,0,0,-1,0,1},ans;char map[25][25];struct status{ int x,y,dep,key; status(int x,int y,int dep,int key):x(x),y(y),dep(dep),key(key) {}};void bfs(int x,int y){ queue<status> Q; Q.push(status(x,y,0,0)); f[x][y][0]=0; bool flag=false; while(!Q.empty()) { if(flag) break; status t=Q.front();Q.pop(); for(int s=0;s<4;s++) { int X=t.x+dir[s][0],Y=t.y+dir[s][1],key=t.key; if(X<1||X>n||Y<1||Y>m||map[X][Y]==‘*‘) continue; if(isupper(map[X][Y])) { int k=map[X][Y]-‘A‘; if(!(key&(1<<k))) continue; } if(islower(map[X][Y])) { int k=map[X][Y]-‘a‘; key=t.key|(1<<k); } if(f[X][Y][key]) continue; f[X][Y][key]=1; if(X==ex&&Y==ey) {flag=true;ans=min(ans,t.dep+1);} Q.push(status(X,Y,t.dep+1,key)); } }}int main(){ //freopen("in.txt","r",stdin); ios::sync_with_stdio(false); string tt; while(cin>>n>>m>>t) { memset(f,0,sizeof(f)); ans=1<<28; 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]==‘@‘) {sx=i;sy=j+1;} if(tt[j]==‘^‘) {ex=i;ey=j+1;} } } bfs(sx,sy); if(ans<t) cout<<ans<<endl; else cout<<"-1"<<endl; }}
| 11876984 | 2014-10-15 13:22:15 | Accepted | 1429 | 562MS | 3664K | 1744 B | C++ | Physcal |
HDU 1429 (BFS+记忆化状压搜索)
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。