?

第一次接触搜索+状态压缩 看了大神的题解 勉强把题目弄懂了。

用二进制来表示手头的钥匙有哪些，100表示有第三把钥匙，111表示有第三、二、一把，搜索下一点时，如果该点为钥匙点，则可采用|运算来

模拟拾取，显然0001 | 1000 = 1001，同理，当为相应的门时采用&运算来模拟开启，例如1101 & 0001 = 0001（即可以打开'A'门）

#include
  
   
#include
   
     #include
    
      using namespace std; int n,m,t,ans; char map[25][25]; int vis[25][25][1030];//标记数组 int dir[4][2]={-1,0,1,0,0,1,0,-1}; //四个方向 struct point { int x,y,step,key; }; point s; int check(int x,int y)//检查 { if(s.x>=0&&s.x
     
      =0&&s.y
      
       q; vis[s.x][s.y][s.key]=1; for(q.push(s);!q.empty();q.pop()) { tp=q.front(); for(int k=0;k<4;k++) { s=tp; //注意这里要先把tp赋值给s，即先把上次搜索到的保存下来，再去扩展。 s.x=tp.x+dir[k][0]; s.y=tp.y+dir[k][1]; if(check(s.x,s.y)&&map[s.x][s.y]!='*'&&!vis[s.x][s.y][s.key]) { if(map[s.x][s.y]=='.'||map[s.x][s.y]=='@') { vis[s.x][s.y][s.key]=1; s.step++; q.push(s); } if(map[s.x][s.y]=='^') { if(s.step+1
       
        ='A'&&map[s.x][s.y]<='J') {//a<<2表示将a是二进制左移2位（相当于*4），这里用来表示钥匙eg:A-A=0;1<<0,就是0000 0001就是第一把钥匙了。 //同理当g[s.x][s.y]='B'时，就是1<<2,就是0000 0010,表示第二把钥匙； int key=1<<(map[s.x][s.y]-'A');//按位于运算，当有对应的钥匙时，等式成立；才能打开门 if(s.key&key) { vis[s.x][s.y][s.key]=1; s.step+=1; q.push(s); } } if(map[s.x][s.y]>='a'&&map[s.x][s.y]<='j') { //按位或运算，吸收钥匙； int key=1<<(map[s.x][s.y]-'a'); if(!vis[s.x][s.y][s.key|key]) { vis[s.x][s.y][s.key|key]=1; s.step+=1; s.key=s.key|key; q.push(s); } } } } } } int main() { while(scanf(%d%d%d,&n,&m,&t)!=EOF) { memset(vis,0,sizeof(vis)); ans=-1; for(int i=0;i
        
         
?