跳到主要内容

864.获取所有钥匙的最短路径

· 阅读需 5 分钟

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、复杂度​

  • 时间复杂度：O(k!∗mn)O(k!*mn)
  • 空间复杂度：O(mn)O(mn)

5、执行结果​

image.png