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;}