题解 | 864. 获取所有钥匙的最短路径
- 获取所有钥匙的最短路径原题链接
题意：
给你一个二维数组grid其中：
| 符号 | 意义 |
|---|---|
| '.' | 代表可走的空房间 |
| '#' | 代表不可走的墙壁 |
| '@' | 代表出发的起点 |
| 'A'~'F' | 代表锁 |
| 'a'~'f' | 代表钥匙 |
求最少用几步可以拿完所有钥匙，如果无法拿到钥匙请输出-1。
做题思路：
本题很明显是最短路问题，但不同的是，多了钥匙这一条件，所以转变为多层图最短路问题。
多层图最短路与常规最短路的区别为，正常最短路的点走过一次就不可以在走了，但对多层图最短路而言，当经过的点状态不同时，
为了处理这多出来的层数，在定义数组时，从原本最短路的二维数组，变为三维数组。
const int N=32,M=1<<6;
struct Index{
//x,y代表点的行和列
//key用来存储钥匙的个数
int x,y,key;
};
//这里要严格注意数组的大小
//N为n,m的大小
//M=1<<6是因为数组中只存在6把钥匙
int d[N][N][M]={0};
//判断在该层点是否出现
bool vis[N][N][M]={0};
//四个移动方向
int dir[5][2]={{1,0},{-1,0},{0,1},{0,-1}};
queue<Index>q;
在定义完数组后，本题的难点在于如何处理辨别钥匙是否匹配，因为每把钥匙可以匹配的锁都不相同，所以无法用单独的计数法，判断是否为该锁的钥匙，这里运用各类运算符，进行锁与钥匙的配对。
int n=grid.size();
int m=grid[0].size();
//keys用来存储总计有几把钥匙
int keys=0;
for (int i=0;i<n;i++)
{
for (int j=0;j<m;j++)
{
//将初始起点放入队列
if (grid[i][j]=='@')q.push({i,j,0});
/*
下方if代码用来判断有几把钥匙
其首先1<<x,为将二进制中的01向左移动x位
如1<<3，就是有原01，向左移动3位，变为1000。
所以1<<(grid[i][j]-'a')的作用，是代表在向左移动第几位上的钥匙就是第几把锁
keys|=1<<(grid[i][j]-'a')中“| ”，为“或 ”
| ：有1出1，代表两个二进制字符串相加时，有1就会得出1
如101 | 001 =101
所以当有6把钥匙时，keys应为111111
*/
if (grid[i][j]>='a' && grid[i][j]<='f')
{
keys|=1<<(grid[i][j]-'a');
}
}
}
在存储完钥匙后，即可开始队列循环。这里题解中，层数的含义需要搞清楚，记录的level是读入的点，准确来说是每次便利读入的点的堆，如图：
以该图为例，此时读入的点的顺序为1|2,3|4,5,6,。level记录的层数为此层数。而vis记录时，说的层，是指钥匙个数发生变动，图进入另一张图。
//level代表第几层
int level=0;
while(!q.empty())
{
//这里一定要单独提出q的长度,因为每次循环都会删去q队列中的值
int size=q.size();
for (int k=0;k<size;k++)
{
Index now,next;
now=q.front();
q.pop();
for (int i=0;i<4;i++)
{
next.x=now.x+dir[i][0];
next.y=now.y+dir[i][1];
next.key=now.key;
//超出地图和碰到墙壁的时候跳过
if (next.x<0 || next.y<0 || next.x>=n || next.y>=m || grid[next.x][next.y]=='#')continue;
//由上方代码可以知道 1<<(grid[next.x][next.y]-'A')代表当前的锁，计算方式同上
//不同的是运算符号"&",该符号为按位计算，由此可以计算该锁是否有钥匙存在
//如当 grid[next.x][next.y]="B"时，1<<1=10
//因此当next.key=101时，B的钥匙不存在
//当next.key=010时，B的钥匙存在
if (grid[next.x][next.y]>='A' && grid[next.x][next.y]<='F' && (next.key & (1<<(grid[next.x][next.y]-'A')))==0)continue;
if (grid[next.x][next.y]>='a' && grid[next.x][next.y]<='f')
{
next.key |= (1<<(grid[next.x][next.y]-'a'));
}
//当收集的钥匙数量等于总数时终止循环
if (next.key==keys)
{
return level+1;
}
//记录该点，避免重复循环
//注意记录的点的第三维是钥匙的个数
//当钥匙数量变动时，点就会进入下一层图，进行扩点，相当于更新地图
if (!vis[next.x][next.y][next.key])
{
q.push({next.x,next.y,next.key});
vis[next.x][next.y][next.key]=1;
}
}
}
//当此层的节点结束没全钥匙找到时，进入下一层，层数加1
level++;
}
return -1;
