题解

难度：偏难

知识点：BFS 状态压缩 队列

思路：

如果不存在钥匙和锁的情况：（理解BFS过程）

（将例子中的小写字母看为1，大写字母看为0）构成数组G[5][5]

1. 起始位置G[0][1]，因此得到b[0][1]=0

【注】辅助数组b[i][j]用来记录从起始位置到坐标（i，j)一共的步数。初始需要将其赋值为-1，表示走到该位置需要的最少步数还没有得到。

2. 从初始位置G[0][1],进行上下左右搜索，即G[0][0],G[0][2],G[1]1判断其值是否为1，如果时路表示从起始走一步即可达，因此将b[0][2]=1,b[1][1]=1。

3. 继续对G[0][2]和G[1][1]上下左右四个方向进行判断，因此可得b[2][1]=2,b[1][2]=2,b[0][3]=2。(在进行赋值之前首先取判断b[i][j]是否等于-1，如果等于才进行赋值，如果不等于说明已经找到了从起始位置到该位置的最小步数，例：G[1][1]向上搜索到G[0][1]此时b[0][1]=0，不能再将值赋值为2)。

4.继续对G[2][1],G[1][2],G[0][3]上下左右进行判断，直到搜索到G[2][4]为止。

本题思路（存在钥匙和锁的情况）

1. 从题目一直最多存在10把锁，如果要记录已经获得的钥匙用那些。方法一：使用一个数组，依次记录每一把钥匙时候获得。方法二：用一个数字来表示得到的钥匙
   0000000001 --钥匙1
   0000000010 --钥匙2
   0000000100 --钥匙3
   0000001000 --钥匙4
   0000010000 --钥匙5
   0000100000 --钥匙6
   0001000000 --钥匙7
   0010000000 --钥匙8
   0100000000 --钥匙9
   1000000000 --钥匙10
   如果已经获得钥匙10、6、3、1即将四把钥匙所对应的数进行异或得：1000100101
   当要判断那一把钥匙是否存在时采用与运算：
   判断是否或得钥匙5：
   1000100101&0000010000=0000000000（为0）
   判断是否获得钥匙6：
   1000100101&0000100000=0000100000（不为0）

2. 不能直接用b[i][j]来判断需要的步数，而是采用更高维的数组b[i][j][k]来记录从初始位置，到位置(i,j)在用钥匙K的情况下需要的步数。

第一轮：

第二轮：

第三轮：

第四轮：

第5轮：

第6轮：

#include<stdio.h>
#include<queue>
#include<string.h>
#include<vector>
using namespace std;
char G[105][105];
int book[105][105][1200],N,M;
int Next[4][2]={0,1,0,-1,1,0,-1,0};
int bfs(int,int);
struct node{
    int x,y,k,step;
    node(int x,int y,int k,int step):x(x),y(y),k(k),step(step){}
};
int main(){
    int i,j;
    //freopen("input.txt","r",stdin);
    while(scanf("%d%d",&N,&M)!=EOF){
        for(i=0;i<N;i++) scanf("%s",G[i]);
        memset(book,0,sizeof(book));
        int flag=0;
        for(i=0;i<N;i++){
            if(flag==1) break;
            for(j=0;j<M;j++)
                if(G[i][j]=='2'){
                    flag=1;
                    book[i][j][0]=1;
                    printf("%d\n",bfs(i,j));
                    break;
                }
        }
    }
}
int bfs(int startX,int startY){
    queue<node> Q;
    Q.push(node(startX,startY,0,0));
    while(!Q.empty()){
        node head=Q.front();Q.pop();
        if(G[head.x][head.y]=='3') return head.step;
        for(int i=0;i<4;i++){
            int nx=head.x+Next[i][0],ny=head.y+Next[i][1];
            if(nx>=N||nx<0||ny>=M||ny<0||G[nx][ny]=='0') continue;
            int key=head.k;
            if('a'<=G[nx][ny]&&G[nx][ny]<='z') key=key|(1<<(G[nx][ny]-'a'));
            if('A'<=G[nx][ny]&&G[nx][ny]<='Z'&&(key&(1<<(G[nx][ny]-'A')))==0) continue;
            if(!book[nx][ny][key]){
                book[nx][ny][key]=1;
                Q.push(node(nx,ny,key,head.step+1));
            }
        }
    }
    return 0;
}