hdu 1429 (bfs+状态压缩) 胜利大逃亡续

http://acm.hdu.edu.cn/showproblem.php?pid=1429

典型的状压搜索,在普通的搜索基础上,利用二进制的特性记录钥匙与门, 二进制的每一位代表一把钥匙,比如说拿到了2号钥匙

那么原有的00000变为了00010,当到大了对应的二号门的时候,利用位运算00010来&上1<<2也就是00010就是非0,如果不是二号门的时候

那么00010&上1<<x都是0,所以此时其它门都进不去,如果再拿到了三号钥匙加上之后变成了00110,代表二号三号钥匙都拿到了,然后到了三号门的

时候00110&(1<<3)00100或者到了二号门的时候00110&(1<<2)00010都是非0的,到其他门都是为0的-----

这样就很好的解决了钥匙的记录问题,这里有10把钥匙,所以数组要大于2的10次方

code

  1 #include<cstdio>
  2 #include<queue>
  3 #include<cstring>
  4 using namespace std;
  5 int dx[]={1,-1,0,0};
  6 int dy[]={0,0,-1,1};
  7 char dzm[]={'A','B','C','D','E','F','G','H','I','J'};
  8 char xzm[]={'a','b','c','d','e','f','g','h','i','j'};
  9 struct point {
 10     int x,y;
 11     int step,dir;
 12 };
 13 int n,m,sx,sy;
 14 int visit[30][30][1050];//记录钥匙
 15 char map[30][30];
 16 int bfs()
 17 {
 18     int i,j;
 19     memset(visit,0,sizeof(visit));
 20     queue<point>Q;
 21     point now,next;
 22     now.x=sx;now.y=sy;
 23     now.step=now.dir=0;
 24     visit[now.x][now.y][now.dir]=1;
 25     Q.push(now);
 26     while (!Q.empty())
 27     {
 28         now=Q.front();
 29         Q.pop();
 30         if (map[now.x][now.y]=='^')
 31             return now.step;
 32         for (i=0;i<4;i++)
 33         {
 34             next.x=now.x+dx[i];
 35             next.y=now.y+dy[i];
 36             next.step=now.step+1;
 37             next.dir=now.dir;
 38             if (map[next.x][next.y]=='*')continue;
 39             if (next.x<1||next.x>n||next.y<1||next.y>m)continue;
 40             if (map[next.x][next.y]<='J'&&map[next.x][next.y]>='A')
 41             {
 42                 for (j=0;j<10;j++)
 43                 {
 44                     if (map[next.x][next.y]==dzm[j])
 45                     {
 46                         if ((next.dir&(1<<j))!=0)
 47                         {
 48                             if (visit[next.x][next.y][next.dir]==0)
 49                             {
 50                                 visit[next.x][next.y][next.dir]=1;
 51                                 Q.push(next);
 52                             }
 53                         }
 54                     }
 55                 }
 56             }
 57             else  if (map[next.x][next.y]<='j'&&map[next.x][next.y]>='a')
 58             {
 59                 for (j=0;j<10;j++)
 60                 {
 61                     if (map[next.x][next.y]==xzm[j])
 62                     {
 63                         if ((next.dir&(1<<j))==0)
 64                             next.dir+=(1<<j);
 65                         if (visit[next.x][next.y][next.dir]==0)
 66                         {
 67                             visit[next.x][next.y][next.dir]=1;
 68                             Q.push(next);
 69                         }
 70                     }
 71                 }
 72             }
 73             else
 74             {
 75                 if (visit[next.x][next.y][next.dir]==0)
 76                 {
 77                     visit[next.x][next.y][next.dir]=1;
 78                     Q.push(next);
 79                 }
 80             }
 81         }
 82     }
 83     return -1;
 84 }
 85 int main()
 86 {
 87     int i,j,t;
 88     while (~scanf("%d %d %d",&n,&m,&t))
 89     {
 90         getchar();
 91         for (i=1;i<=n;i++)
 92         {
 93             for (j=1;j<=m;j++)
 94             {
 95                 scanf(" %c",&map[i][j]);
 96                 if (map[i][j]=='@')
 97                     sx=i,sy=j;
 98             }
 99         }
100         int q=bfs();
101         if (q>=t)
102             printf("-1
");
103         else
104             printf("%d
",q);
105     }
106     return 0;
107 }