链接
给定一个二维网格 grid ，其中：
- ‘.’ 代表一个空房间
- ‘#’ 代表一堵墙
- ‘@’ 是起点
- 小写字母代表钥匙
- 大写字母代表锁
我们从起点开始出发，一次移动是指向四个基本方向之一行走一个单位空间。我们不能在网格外面行走，也无法穿过一堵墙。如果途经一个钥匙，我们就把它捡起来。除非我们手里有对应的钥匙，否则无法通过锁。
假设 k 为 钥匙/锁 的个数，且满足 1 <= k <= 6，字母表中的前 k 个字母在网格中都有自己对应的一个小写和一个大写字母。换言之，每个锁有唯一对应的钥匙，每个钥匙也有唯一对应的锁。另外，代表钥匙和锁的字母互为大小写并按字母顺序排列。
返回获取所有钥匙所需要的移动的最少次数。如果无法获取所有钥匙，返回 -1 。
分层图BFS，地图多了一维钥匙状态。在新的地图上跑BFS。
状态压缩，钥匙的状态转化为一个二进制数，1表示有，0表示没有，再转化为10进制数。
若有第n把钥匙，第三维空间开2的n次。
struct node {
int x, y, k, step;
};
int dir[4][2] = {
{1,0},{0,1},{0,-1},{-1,0}
};
class Solution {
public:
int shortestPathAllKeys(vector<string>& grid) {
int n = grid.size(), m = grid[0].size();
int key = 0;
node t;
t.k = 0, t.step = 0;
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
if (grid[i][j] == '@') {
t.x = i, t.y = j;
} else if (grid[i][j] >= 'a' && grid[i][j] <= 'f') {
key |= 1 << (grid[i][j] - 'a');
}
}
}
bool vis[n][m][2 << 6];
memset(vis, 0, sizeof(vis));
queue<node> q;
q.push(t);
vis[t.x][t.y][0] = true;
while (q.size()) {
t = q.front();
q.pop();
for (int i = 0; i < 4; i++) {
int xx = t.x + dir[i][0], yy = t.y + dir[i][1], kk = t.k;
if (xx < 0 || xx >= n || yy < 0 || yy >= m || vis[xx][yy][kk] || grid[xx][yy] == '#') continue;
if (grid[xx][yy] >= 'A' && grid[xx][yy] <= 'F' && !((1 << (grid[xx][yy] - 'A')) & kk)) continue;
if (grid[xx][yy] >= 'a' && grid[xx][yy] <= 'f') {
kk |= 1 << (grid[xx][yy] - 'a');
if (kk == key) {
return t.step + 1;
}
}
q.push({ xx,yy,kk,t.step + 1 });
vis[xx][yy][kk] = true;
}
}
return -1;
}
};