胜利大逃亡(续)

  1 #include<iostream>
  2 #include<stdio.h>
  3 #include<string.h>
  4 #include<queue>
  5 using namespace std;
  6 int dir[][2]={{1,0},{0,1},{-1,0},{0,-1}};
  7 struct node
  8 {
  9     int x,y;
 10     int cnt;
 11     int time;
 12 };
 13 char map[22][22];
 14 int flag[2048][22][22];
 15 int x1,y1;
 16 int row,col,t;
 17 queue<node>q;
 18 
 19 bool judge(node tp)
 20 {
 21     if(tp.x<0 || tp.x>=row || tp.y<0 || tp.y>=col || map[tp.x][tp.y]=='*')
 22         return false;
 23     return true;
 24 }
 25 
 26 int bfs()
 27 {
 28     while(!q.empty())
 29         q.pop();
 30     node temp,p;
 31     int i,cc;
 32     p.x=x1;
 33     p.y=y1;
 34     p.cnt=0;
 35     p.time=0;
 36     q.push(p);
 37     while(!q.empty())
 38     {
 39         p=q.front();
 40         q.pop();
 41         if(p.time>=t-1)
 42             return -1;
 43         for(i=0;i<4;i++)
 44         {
 45             temp=p;
 46             temp.x+=dir[i][0];
 47             temp.y+=dir[i][1];
 48             temp.time=p.time+1;
 49             temp.cnt=p.cnt;
 50             if(!judge(temp))
 51                 continue;
 52             if(map[temp.x][temp.y]=='^')
 53             {
 54                 return temp.time;
 55             }
 56             if(map[temp.x][temp.y]=='@' || map[temp.x][temp.y]=='.')
 57             {
 58                 if(!flag[temp.cnt][temp.x][temp.y])
 59                 {
 60                     flag[temp.cnt][temp.x][temp.y]=1;
 61                     q.push(temp);
 62                 }
 63                 continue;
 64             }
 65             if(map[temp.x][temp.y]>='A' && map[temp.x][temp.y]<='J' && !flag[temp.cnt][temp.x][temp.y])
 66             {
 67                 cc=temp.cnt;
 68                 if((cc>>(map[temp.x][temp.y]-'A')) & 1)
 69                 {
 70                     flag[temp.cnt][temp.x][temp.y]=1;
 71                     q.push(temp);
 72                 }
 73                 continue;
 74             }
 75             if(map[temp.x][temp.y]>='a' && map[temp.x][temp.y]<='j')
 76             {
 77                 cc=1<<(map[temp.x][temp.y]-'a');
 78                 temp.cnt=cc | temp.cnt;
 79                 if(!flag[temp.cnt][temp.x][temp.y])
 80                 {
 81                     flag[temp.cnt][temp.x][temp.y]=1;
 82                     q.push(temp);
 83                 }
 84                 continue;
 85             }
 86         }
 87     }
 88     return -1;
 89 }
 90 
 91 int main()
 92 {
 93     while(~scanf("%d%d%d",&row,&col,&t))
 94     {
 95         int i,j;
 96         bool ff=false;
 97         for(i=0;i<row;i++)
 98         {
 99             scanf("%s",map[i]);
100             if(!ff)
101             {
102                 for(j=0;j<col;j++)
103                 {
104                     if(map[i][j]=='@')
105                     {
106                         x1=i;
107                         y1=j;
108                         ff=true;
109                         break;
110                     }
111                 }
112             }
113         }
114         memset(flag,0,sizeof(flag));
115         flag[0][x1][y1]=1;
116         int res=bfs();
117         printf("%d\n",res);
118     }
119     return 0;
120 }

这是一道简单的状态标记广搜题目，刚开始卡死在状态那个地方，后来想通了，题目中最多拥有10把钥匙，也就是2^10方（十位二进制中的每一位代表着不同钥匙，0代表没有拥有，1代表拥有此钥匙）作为状态标记，所以定义一个三维的flag[][][]标记函数，进行普通的广搜，注意遇到小写字母的时候记得进行左移 再与前一个状态值进行或运算，例如，假设已经用了A 门的要是，状态此时因该是0000000001，意思是拥有了a，如果下一次遇到了J门的钥匙，也就是j，那就应该是(1<<10) | (0000000001),那么此时的状态应该是1000000001，当遇到已经拥有钥匙的门的时候再进行右移运算，例如下一次遇到J门时，我们应该先将1000000001右移10位再与 1进行（&）与运算，如果拥有J门的钥匙 应该是1&1=1 ，是真值，可以通过，如果没有，则0&1=0，是假值，则无法通过。

剩下的就是一般的左右上下的移动 判断。

值得让我吸取教训的是，在定义了一个队列的时候，在使用前必须判断队列里面是否为空，如果不为空，则必须置空，也就是这里让我WA了两三次，就是少了

while(!q.empty())
q.pop();

这一句。

写下这篇来告诫自己下次小心。

赞赏

长按二维码向我转账

受苹果公司新规定影响，微信 iOS 版的赞赏功能被关闭，可通过二维码转账支持公众号。