首页 > 代码库 > HDU 1885 Key Task
HDU 1885 Key Task
bfs。 一把某种颜色的锁开 所有这个颜色的门。
状态检查压缩一下 vis[][][2^4];
跟HDU 1429 类似。至于颜色判断我用了 map;
#include<cstdio> #include<cstring> #include<string> #include<queue> #include<algorithm> #include<map> #include<stack> #include<iostream> #include<list> #include<set> #include<vector> #include<cmath> #define INF 0x7fffffff #define eps 1e-8 #define LL long long #define PI 3.141592654 #define CLR(a,b) memset(a,b,sizeof(a)) #define FOR(i,a,n) for(int i= a;i< n ;i++) #define FOR0(i,a,b) for(int i=a;i>=b;i--) #define pb push_back #define mp make_pair #define ft first #define sd second #define sf scanf #define pf printf #define acfun std::ios::sync_with_stdio(false) #define SIZE 100+1 using namespace std; int xx[]={0,0,-1,1}; int yy[]={-1,1,0,0}; int n,m; char g[SIZE][SIZE]; map<char,int>Mykey; struct lx { int x,y; int t; int key; void init(int xx,int yy,int tt,int kk) { x=xx,y=yy,t=tt,key=kk; } }start; int num[]={8,4,2,1}; bool cheack(char c,int key) { //g r y b bool unlock[4]; FOR(i,0,4) { if(key>=num[i]) { unlock[i]=1; key-=num[i]; } else unlock[i]=0; } int tmp=Mykey[c]; int ans=3; while(tmp>1) { tmp/=2; ans--; } return unlock[ans]; } void bfs() { bool vis[SIZE][SIZE][16]; CLR(vis,0); vis[start.x][start.y][start.key]=1; queue<lx>q; q.push(start); while(!q.empty()) { lx tmp=q.front(); q.pop(); //pf("%d %d time=%d\n",tmp.x,tmp.y,tmp.t); if(g[tmp.x][tmp.y]=='X') { pf("Escape possible in %d steps.\n",tmp.t); return; } FOR(k,0,4) { int x=tmp.x+xx[k]; int y=tmp.y+yy[k]; int key=tmp.key; if(x<0||y<0||x>=n||y>=m||g[x][y]=='#')continue; if(g[x][y]>='a'&&g[x][y]<='z'&&!cheack(g[x][y],key)) key+=Mykey[ g[x][y] ]; else if(g[x][y]>='A'&&g[x][y]<='Z'&&g[x][y]!='X') { if(!cheack(g[x][y]-'A'+'a',key))continue; } if(vis[x][y][key])continue; lx now; now.init(x,y,tmp.t+1,key); vis[x][y][key]=1; q.push(now); } } puts("The poor student is trapped!"); } int main() { Mykey['b']=1; Mykey['y']=2; Mykey['r']=4; Mykey['g']=8; while(~sf("%d%d",&n,&m),n||m) { FOR(i,0,n) { char str[SIZE]; sf("%s",str); FOR(j,0,m) { g[i][j]=str[j]; if(str[j]=='*') start.init(i,j,0,0); } } bfs(); } }
HDU 1885 Key Task
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。