HDU 1885 Key Task
來源：程序員人生 發(fā)布時間：2014-11-11 09:02:47 閱讀次數(shù)：2248次
bfs。 1把某種色彩的鎖開 所有這個色彩的門。
狀態(tài)檢查緊縮1下 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⑻
#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};
int yy[]={⑴,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
",tmp.x,tmp.y,tmp.t);
if(g[tmp.x][tmp.y]=='X')
{
pf("Escape possible in %d steps.
",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();
}
}
生活不易，碼農(nóng)辛苦
如果您覺得本網(wǎng)站對您的學(xué)習(xí)有所幫助,可以手機掃描二維碼進行捐贈
