首页 > 代码库 > HDU 1429
HDU 1429
http://acm.hdu.edu.cn/showproblem.php?pid=1429
经典的找钥匙开门走迷宫问题,把钥匙状态压缩一下,然后对迷宫bfs
#include <iostream>#include <cstdio>#include <cstdlib>#include <cstring>#include <queue>using namespace std;int n,m,t;int vis[25][25][1<<10];struct node{ int x,y,s,step;};char M[25][25];int dx[]={1,-1,0,0};int dy[]={0,0,1,-1};int gao(int x,int k){ return (x>>k)&1;}int bfs(node s){ queue <node> q; q.push(s); memset(vis,0,sizeof(vis)); vis[s.x][s.y][0]=1; while(!q.empty()){ node u=q.front(); q.pop(); if(M[u.x][u.y]==‘^‘){ return u.step; } for(int i=0;i<4;i++){ int xx=u.x+dx[i]; int yy=u.y+dy[i]; if(xx<0 || xx>=n || yy<0 || yy>=m)continue; if(M[xx][yy]==‘*‘)continue; if(M[xx][yy]>=‘A‘ && M[xx][yy]<=‘J‘ && !(gao(u.s,M[xx][yy]-‘A‘)))continue; node next=u; if(M[xx][yy]>=‘a‘ && M[xx][yy]<=‘j‘){ if(!gao(u.s,M[xx][yy]-‘a‘)){ next.x=xx;next.y=yy;next.step++;next.s|=(1<<(M[xx][yy]-‘a‘)); if(next.step<t && !vis[xx][yy][next.s]){ vis[xx][yy][next.s]=1; q.push(next); } } else{ next.x=xx;next.y=yy;next.step++; if(!vis[xx][yy][u.s] && next.step<t){ vis[xx][yy][next.s]=1; q.push(next); } } } else{ next.x=xx;next.y=yy;next.step++; if(next.step<t && !vis[xx][yy][next.s]){ vis[xx][yy][next.s]=1; q.push(next); } } } } return -1;}int main(){ while(~scanf("%d%d%d",&n,&m,&t)){ for(int i=0;i<n;i++) scanf("%s",M[i]); node s; for(int i=0;i<n;i++) for(int j=0;j<m;j++) if(M[i][j]==‘@‘) s.x=i,s.y=j; s.s=0;s.step=0; printf("%d\n",bfs(s)); } return 0;}
HDU 1429
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。