HDU 1429 胜利大逃亡(续) BFS+位运算
题意很简单。
用一个十位的二进制数表示钥匙，如00000000001代表有第一个钥匙，0000000010代表第二个钥匙。
假设拿到1，2钥匙，则为0000000011。可以采用位运算的|。
拿到钥匙，key=key|(1<<nextkey);
判断是否有这个钥匙，(key>>nextkey)&1是否为0，如果是0则没有这把钥匙。
用一个 三维visit表示状态。
#include <iostream>#include <cstdio>#include <algorithm>#include <string>#include <cmath>#include <cstring>#include <queue>#include <set>#include <vector>#include <stack>#include <map>#include <iomanip>#define PI acos(-1.0)#define Max 2005#define inf 1<<28#define LL(x) (x<<1)#define RR(x) (x<<1|1)#define ll long longusing namespace std;struct kdq{ int x,y,step; int key;} q[1000000];int n,m,t;char Map[30][30];int inMap(kdq a){ if(a.x>=0&&a.x<n&&a.y>=0&&a.y<m&&Map[a.x][a.y]!='*') return 1; return 0;}bool visit[30][30][1200];int movex[4]= {0,0,1,-1};int movey[4]= {1,-1,0,0};int bfs(kdq s){ int num=0,cnt=0; q[num++]=s; visit[s.x][s.y][0]=1; while(num>cnt) { kdq temp=q[cnt++]; if(Map[temp.x][temp.y]=='^') { if(temp.step>=t) return -1; return temp.step; } if(temp.step>=t) return -1; for(int i=0; i<4; i++) { kdq tt; tt.x=movex[i]+temp.x; tt.y=movey[i]+temp.y; tt.key=temp.key; tt.step=temp.step+1; if(inMap(tt)) { if(islower(Map[tt.x][tt.y]))//a-j { int key=1<<(Map[tt.x][tt.y]-'a'); tt.key=tt.key|key;//拿到这把钥匙 } else if(isupper(Map[tt.x][tt.y]))//A-J { int key=Map[tt.x][tt.y]-'A'; if(((tt.key>>key)&1)==0)//如果没这把钥匙 continue; } if(!visit[tt.x][tt.y][tt.key]) { visit[tt.x][tt.y][tt.key]=1; q[num++]=tt; } } } } return -1;}int main(){ char x; int sx,sy; while(scanf("%d%d%d",&n,&m,&t)!=EOF) { memset(visit,0,sizeof(visit)); for(int i=0; i<n; i++) { //scanf("%s",Map[i]); for(int j=0; j<m; j++) { cin>>Map[i][j]; if(Map[i][j]=='@') { sx=i,sy=j; } } } kdq s; s.x=sx,s.y=sy,s.step=0,s.key=0; printf("%d\n",bfs(s)); } return 0;}