1、题干
给定一个二维网格 grid
,其中:
- '.' 代表一个空房间
- '#' 代表一堵墙
- '@' 是起点
- 小写字母代表钥匙
- 大写字母代表锁
我们从起点开始出发,一次移动是指向四个基本方向之一行走一个单位空间。我们不能在网格外面行走,也无法穿过一堵墙。如果途经一个钥匙,我们就把它捡起来。除非我们手里有对应的钥匙,否则无法通过锁。
假设 k 为 钥匙/锁 的个数,且满足 1 <= k <= 6
,字母表中的前 k
个字母在网格中都有自己对应的一个小写和一个大写字母。换言之,每个锁有唯一对应的钥匙,每个钥匙也有唯一对应的锁。另外,代表钥匙和锁的字母互为大小写并按字母顺序排列。
返回获取所有钥匙所需要的移动的最少次数。如果无法获取所有钥匙,返回 -1
。
示例 1:
输入:grid = ["@.a..","###.#","b.A.B"]
输出:8
解释:目标是获得所有钥匙,而不是打开所有锁。
示例 2:
输入:grid = ["@..aA","..B#.","....b"]
输出:6
示例 3:
输入: grid = ["@Aa"]
输出: -1
提示:
m == grid.length
n == grid[i].length
1 <= m, n <= 30
grid[i][j]
只含有'.'
,'#'
,'@'
,'a'-
'f
'
以及'A'-'F'
- 钥匙的数目范围是
[1, 6]
- 每个钥匙都对应一个 不同 的字母
- 每个钥匙正好打开一个对应的锁
Problem: 864. 获取所有钥匙的最短路径
2、思路
写过最长的代码,心态崩了
思路:
- 回溯,对所有钥匙进行排列组合,得到所有路径(不校验路径是否连通)
- 遍历所有路径,累计从起点经过所有钥匙需要的步数,结果取最小步数
- 广搜计算两把钥匙之间的最短路径(需要校验路径是否连通)
3、Code
function shortestPathAllKeys(grid: string[]): number {
const m = grid.length, n = grid[0].length;
const M = 10007;
const encode = (i: number, j: number) => i * M + j;
const decode = (d: number) => [(d / M) >> 0, d % M];
let start = 0;
const keys: number[] = [];
for (let i = 0; i < m; i++) {
for (let j = 0; j < n; j++) {
if (grid[i][j] === "@") start = encode(i, j);
if (grid[i][j] >= "a" && grid[i][j] <= "f") keys.push(encode(i, j));
}
}
// 寻找两把钥匙之间的最短路径
function bfs(source: number, target: number, visited: Set<number>, foundKeys: Set<string>): number {
let queue = [source];
const [ti, tj] = decode(target);
let step = 1;
while (queue.length) {
const nextQueue = new Set<number>();
for (const q of queue) {
if (visited.has(q)) continue;
visited.add(q);
const [qi, qj] = decode(q);
const dirs = [[qi, qj + 1], [qi, qj - 1], [qi + 1, qj], [qi - 1, qj],];
for (const [i, j] of dirs) {
if (!grid[i] || !grid[i][j] || grid[i][j] === "#") continue;
if (grid[i][j] >= "A" && grid[i][j] <= "F" && !foundKeys.has(grid[i][j].toLowerCase())) continue;
if (i === ti && j === tj) return step;
nextQueue.add(encode(i, j));
}
}
step++;
queue = [...nextQueue];
}
return 0;
}
// 遍历所有路径,累计从起点经过所有钥匙需要的步数,结果取最小步数
let res = Infinity;
function calcSteps(path: Set<number>) {
let step = 0, source = start, foundKeys = new Set<string>();
for (const p of path) {
const st = bfs(source, p, new Set(), foundKeys);
step += st;
if (!st || step >= res) return;
const [pi, pj] = decode(p);
foundKeys.add(grid[pi][pj]);
source = p;
}
if (step < res) res = step;
}
// 对钥匙进行排列组合
function dfs(path: Set<number>) {
for (const k of keys) {
if (path.has(k)) continue;
path.add(k);
dfs(path);
if (path.size === keys.length) calcSteps(path);
path.delete(k);
}
}
dfs(new Set());
return res === Infinity ? -1 : res;
}
4、复杂度
- 时间复杂度:
- 空间复杂度: