题目简介：
给定一个二维网格 grid ，其中：
- ‘.’ 代表一个空房间
- ‘#’ 代表一堵墙
- ‘@’ 是起点
- 小写字母代表钥匙
- 大写字母代表锁
我们从起点开始出发，一次移动是指向四个基本方向之一行走一个单位空间。我们不能在网格外面行走，也无法穿过一堵墙。如果途经一个钥匙，我们就把它捡起来。除非我们手里有对应的钥匙，否则无法通过锁。
假设 k 为 钥匙/锁 的个数，且满足 1 <= k <= 6，字母表中的前 k 个字母在网格中都有自己对应的一个小写和一个大写字母。换言之，每个锁有唯一对应的钥匙，每个钥匙也有唯一对应的锁。另外，代表钥匙和锁的字母互为大小写并按字母顺序排列。
返回获取所有钥匙所需要的移动的最少次数。如果无法获取所有钥匙，返回 -1 。
示例 1：
1
2
3
| 输入：grid = ["@.a.#","###.#","b.A.B"]
输出：8
解释：目标是获得所有钥匙，而不是打开所有锁。
|
提示：
m == grid.lengthn == grid[i].length1 <= m, n <= 30grid[i][j] 只含有 '.', '#', '@', 'a'-``'f``' 以及 'A'-'F'- 钥匙的数目范围是
[1, 6]
- 每个钥匙都对应一个 不同 的字母
- 每个钥匙正好打开一个对应的锁
思路：
首先我们可以用BFS来获得起点到终点的一条路径，但是由于有锁和钥匙，所以我们进行状态压缩。
如100代表我们获得了c钥匙，但是没有获得a，b钥匙（从低位开始为a）。
我们定义一个队列 qu 来存储当前位置以及当前拥有的钥匙的状态，即 (i, j, state)，其中 (i, j) 表示当前位置，state 表示当前拥有的钥匙的状态，即 state 的第 i 位为 1 表示当前拥有第 i 把钥匙，否则表示当前没有第 i 把钥匙。
另外，定义数组 visit 记录当前位置以及当前拥有的钥匙的状态是否已经被访问过，如果访问过，则不需要再次访问。
在广度优先搜索的过程中，我们每次从队首取出一个位置 (i, j, state)，并判断当前位置是否为终点，即当前位置是否拥有所有的钥匙，即 state 的二进制表示中的 1 的个数是否为 key。如果是，将当前步数作为答案返回。
否则，我们从当前位置出发，往上下左右四个方向走，如果可以走到下一个位置 (x, y)，则将 (x, y, next_state) 加入队列 qu，其中 next_state 表示下一个位置的钥匙的状态。
若走到墙壁或者走到锁但是没有对应的钥匙时，则continue。
搜索结束，没有找到所有钥匙，则返回-1。
代码如下：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
| class Solution {
public:
int shortestPathAllKeys(vector<string>& grid) {
int sx, sy;
int key = 0;
int res = 0;
for(int i = 0; i < grid.size(); i++){
for(int j = 0; j < grid[i].size(); j++){
if(grid[i][j] == '@'){
sx = i;
sy = j;
}
if(islower(grid[i][j]))
key++;
}
}
vector<vector<vector<bool>>> visit(grid.size(),
vector<vector<bool>>(grid[0].size()
, vector<bool>(1 << key)));
queue<tuple<int, int, int>> qu{{{sx, sy, 0}}};
visit[sx][sy][0] = true;
int dx[4] = {0, 1, 0, -1};
int dy[4] = {-1, 0, 1, 0};
while(!qu.empty()){
int size = qu.size();
for(int i = 0; i < size; i++){
auto [now_i, now_j, now_state] = qu.front();
qu.pop();
if(now_state == (1 << key) - 1)
return res;
for(int j = 0; j < 4; j++){
int now_x = now_i + dx[j];
int now_y = now_j + dy[j];
if(now_x < 0 || now_x >= grid.size() || now_y < 0
|| now_y >= grid[0].size())
continue;
if(grid[now_x][now_y] == '#')
continue;
if(isupper(grid[now_x][now_y]) &&
(now_state >> (grid[now_x][now_y] - 'A') & 1) == 0)
continue;
int next_state = now_state;
if(islower(grid[now_x][now_y]))
next_state |= 1 << (grid[now_x][now_y] - 'a');
if(!visit[now_x][now_y][next_state]){
visit[now_x][now_y][next_state] = true;
qu.push({now_x, now_y, next_state});
}
}
}
res++;
}
return -1;
}
};
|
