LeetCode 864. 获取所有钥匙的最短路径
题目描述
题意分析
网格中
@为起点、#为墙、.为空地，小写字母是钥匙，大写字母是对应的门。每步上下左右移动一格，钥匙拿到后一直保留，只有持有对应钥匙才能经过门。求收集全部钥匙的最少步数，不要求走过所有门或返回起点；无法完成则返回-1。钥匙至多 6 种，按题意从a连续编号。
解法：位置与钥匙集合组成 BFS 状态
核心思路
[!blue]
普通网格搜索只记录位置，但这里拿到新钥匙后，可能需要返回之前走过的位置，才能通过原先打不开的门。因此状态必须是
(行, 列, 已有钥匙集合)；位置与钥匙都相同，后续可行移动才完全相同，可以合并去重。钥匙的获得顺序不会影响后续，不必保存在状态中。用整数
mask压缩钥匙集合：第k位为 1 表示持有第k把钥匙。进入小写字母格时，用mask |= 1 << (ch - 'a')加入钥匙，重复经过也不会重复计数；遇到大写门时，检查对应位是否为 1，没有就不能进入。扫描全部钥匙得到目标goal，题目连续编号使它等于2^K - 1，因此状态数组的第三维开goal + 1即可覆盖所有集合。每次合法移动都只花一步，所以在这个扩展状态图上使用 BFS。从
(起点, 0)出发，对四个方向先排除越界、墙和未解锁的门，再更新落点钥匙，最后用更新后的完整状态查重并入队。钥匙是在进入格子时自动获得的，不额外消耗一步，所以访问标记也必须使用拾取后的集合。队列每层对应相同的移动步数。Java 在层开始时固定队列大小，Go 固定本层结束下标
end，新加入的状态都留到下一层。状态首次入队时已经以最少步数到达，之后同状态的更长路径无需重复展开；第一次取出mask == goal的状态，就得到收齐钥匙的最短距离。如果队列耗尽仍没有达到目标，说明所有可达的位置与钥匙组合都已尝试，不存在合法收集路线，返回
-1。
解题步骤
- 扫描起点和全部钥匙，建立目标掩码。
- 将
(起点, 0)入队并标记访问，初始距离为 0。- 逐层取出状态，钥匙集合等于目标时返回当前层距离。
- 枚举四邻格，检查通行条件，拾取落点钥匙，再把未访问的新状态标记并加入下一层。
- 当前层处理完后距离加一；队列为空仍未成功则返回
-1。
代码实现
class Solution {
public int shortestPathAllKeys(String[] grid) {
int m = grid.length;
int n = grid[0].length();
int startR = 0;
int startC = 0;
int goal = 0;
for (int r = 0; r < m; r++) {
for (int c = 0; c < n; c++) {
char ch = grid[r].charAt(c);
if (ch == '@') {
startR = r;
startC = c;
}
if (ch >= 'a' && ch <= 'f') {
goal |= 1 << (ch - 'a');
}
}
}
boolean[][][] seen = new boolean[m][n][goal + 1];
Deque<int[]> queue = new ArrayDeque<>();
queue.add(new int[] {
startR,
startC,
0
});
seen[startR][startC][0] = true;
int[] dirs = {
-1,
0,
1,
0,
-1
};
for (int steps = 0; !queue.isEmpty(); steps++) {
for (int size = queue.size(); size > 0; size--) {
int[] state = queue.remove();
if (state[2] == goal) {
return steps;
}
for (int d = 0; d < 4; d++) {
int r = state[0] + dirs[d];
int c = state[1] + dirs[d + 1];
int mask = state[2];
if (r < 0 || r >= m || c < 0 || c >= n) {
continue;
}
char ch = grid[r].charAt(c);
if (ch == '#') {
continue;
}
if (ch >= 'A' && ch <= 'F' && (mask & (1 << (ch - 'A'))) == 0) {
continue;
}
if (ch >= 'a' && ch <= 'f') {
mask |= 1 << (ch - 'a');
}
if (!seen[r][c][mask]) {
seen[r][c][mask] = true;
queue.add(new int[] {
r,
c,
mask
});
}
}
}
}
return -1;
}
}
func shortestPathAllKeys(grid []string) int {
m, n := len(grid), len(grid[0])
startR, startC, goal := 0, 0, 0
for r := 0; r < m; r++ {
for c := 0; c < n; c++ {
ch := grid[r][c]
if ch == '@' {
startR, startC = r, c
}
if ch >= 'a' && ch <= 'f' {
goal |= 1 << (ch - 'a')
}
}
}
seen := make([][][]bool, m)
for r := range seen {
seen[r] = make([][]bool, n)
for c := range seen[r] {
seen[r][c] = make([]bool, goal+1)
}
}
queue := [][3]int{
{
startR,
startC,
0,
},
}
seen[startR][startC][0] = true
head := 0
dirs := []int{
-1,
0,
1,
0,
-1,
}
for steps := 0; head < len(queue); steps++ {
end := len(queue)
for head < end {
state := queue[head]
head++
if state[2] == goal {
return steps
}
for d := 0; d < 4; d++ {
r, c, mask := state[0]+dirs[d], state[1]+dirs[d+1], state[2]
if r < 0 || r >= m || c < 0 || c >= n {
continue
}
ch := grid[r][c]
if ch == '#' {
continue
}
if ch >= 'A' && ch <= 'F' && mask&(1<<(ch-'A')) == 0 {
continue
}
if ch >= 'a' && ch <= 'f' {
mask |= 1 << (ch - 'a')
}
if !seen[r][c][mask] {
seen[r][c][mask] = true
queue = append(queue, [3]int{
r,
c,
mask,
})
}
}
}
}
return -1
}
复杂度分析
- 时间复杂度：$O(mn2^K)$，每个状态最多入队一次，只尝试四个方向。
- 空间复杂度：$O(mn2^K)$，用于三维访问数组和搜索队列。
钥匙数为 $K$，最多 $mn2^K$ 个状态。
关键点总结
[!green]
位置决定相邻格子，钥匙集合决定哪些门可以通过，两者合起来才是完整状态。每条边代价相同，分层 BFS 才能直接用层号表示最短距离。
易错点总结
[!yellow]
- 只按坐标标记会禁止拿钥匙后返回旧位置，从而漏解。
- 必须用拾取后的掩码检查并登记新状态。
- 目标是收集全部钥匙，不要求把所有门都走过。
- 每个方向都从当前状态的原掩码开始，不能让上一条候选分支拿到的钥匙影响另一条分支。
相似题目
| 题目 | 难度 | 关联与区别 |
|---|---|---|
| 847. 访问所有节点的最短路径 | 困难 | 同样用位置与已收集集合做状态 BFS，原题收集已访问节点，本题收集改变通行能力的钥匙。 |
| 752. 打开转盘锁 | 中等 | 复用单位代价状态图的分层搜索，但本题状态除位置外还包含钥匙集合。 |