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

题目描述

这是 LeetCode 上的 864. 获取所有钥匙的最短路径 ，难度为困难。

给定一个二维网格 g，其中：

'.' 代表一个空房间
'#' 代表一堵墙
'@' 是起点
小写字母代表钥匙
大写字母代表锁

我们从起点开始出发，一次移动是指向四个基本方向之一行走一个单位空间。

我们不能在网格外面行走，也无法穿过一堵墙。

如果途经一个钥匙，我们就把它捡起来，除非我们手里有对应的钥匙，否则无法通过锁。

假设 k 为钥匙/锁的个数，且满足 $1 <= k <= 6$，字母表中的前 k 个字母在网格中都有自己对应的一个小写和一个大写字母。

换言之，每个锁有唯一对应的钥匙，每个钥匙也有唯一对应的锁。另外，代表钥匙和锁的字母互为大小写并按字母顺序排列。

返回获取所有钥匙所需要的移动的最少次数。

如果无法获取所有钥匙，返回 -1 。

示例 1：

输入：g = ["@.a.#","###.#","b.A.B"]

输出：8

解释：目标是获得所有钥匙，而不是打开所有锁。

示例 2：

1
2
3

输入：g = ["@..aA","..B#.","....b"]

输出：6

示例 3:

1
2
3

输入: g = ["@Aa"]

输出: -1

提示：

$m = g.length$
$n = g[i].length$
$1 <= m, n <= 30$
g[i][j] 只含有 '.','#', '@', 'a'-'f' 以及 'A'-'F'
钥匙的数目范围是 $[1, 6]$
每个钥匙都对应一个不同的字母
每个钥匙正好打开一个对应的锁

BFS + 状态压缩

一道常规的 BFS 运用题，只不过需要在 BFS 过程中记录收集到的钥匙状态。

利用「钥匙数量不超过 $6$，并按字母顺序排列」，我们可以使用一个 int 类型二进制数 state 来代指当前收集到钥匙情况：

若 state 的二进制中的第 $k$ 位为 1，代表当前种类编号为 $k$ 的钥匙 已被收集，后续移动若遇到对应的锁则 能通过
若 state 的二进制中的第 $k$ 位为 0，代表当前种类编号为 $k$ 的钥匙 未被收集，后续移动若遇到对应的锁则 无法通过

其中「钥匙种类编号」则按照小写字母先后顺序，从 $0$ 开始进行划分对应：即字符为 a 的钥匙编号为 0，字符为 b 的钥匙编号为 1，字符为 c 的钥匙编号为 2 …

当使用了这样的「状态压缩」技巧后，我们可以很方便通过「位运算」进行 钥匙检测 和 更新钥匙收集状态：

钥匙检测：(state >> k) & 1，若返回 1 说明第 $k$ 位为 1，当前持有种类编号为 k 的钥匙
更新钥匙收集状态：state |= 1 << k，将 state 的第 $k$ 位设置为 1，代表当前新收集到种类编号为 k 的钥匙

搞明白如何记录当前收集到的钥匙状态后，剩下的则是常规 BFS 过程：

起始遍历一次棋盘，找到起点位置，并将其进行入队，队列维护的是 $(x, y, state)$ 三元组状态（其中 $(x, y)$ 代表当前所在的棋盘位置，$state$ 代表当前的钥匙收集情况）
同时统计整个棋盘所包含的钥匙数量 cnt，并使用数组/哈希表记录到达每个状态所需要消耗的最小步数 step
进行四联通方向的 BFS，转移过程中需要注意「遇到锁时，必须有对应钥匙才能通过」&「遇到钥匙时，需要更新对应的 state 再进行入队」
当 BFS 过程中遇到 state = (1 << cnt) - 1 时，代表所有钥匙均被收集完成，可结束搜索

Java 代码：

class Solution {
    static int N = 35, K = 10, INF = 0x3f3f3f3f;
    static int[][][] dist = new int[N][N][1 << K];
    static int[][] dirs = new int[][]{{1,0},{-1,0},{0,1},{0,-1}};
    public int shortestPathAllKeys(String[] g) {
        int n = g.length, m = g[0].length(), cnt = 0;
        Deque<int[]> d = new ArrayDeque<>();
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                Arrays.fill(dist[i][j], INF);
                char c = g[i].charAt(j);
                if (c == '@') {
                    d.addLast(new int[]{i, j, 0});
                    dist[i][j][0] = 0;
                } else if (c >= 'a' && c <= 'z') cnt++;
            }
        }
        while (!d.isEmpty()) {
            int[] info = d.pollFirst();
            int x = info[0], y = info[1], cur = info[2], step = dist[x][y][cur];
            for (int[] di : dirs) {
                int nx = x + di[0], ny = y + di[1];
                if (nx < 0 || nx >= n || ny < 0 || ny >= m) continue;
                char c = g[nx].charAt(ny);
                if (c == '#') continue;
                if ((c >= 'A' && c <= 'Z') && (cur >> (c - 'A') & 1) == 0) continue;
                int ncur = cur;
                if (c >= 'a' && c <= 'z') ncur |= 1 << (c - 'a');
                if (ncur == (1 << cnt) - 1) return step + 1;
                if (step + 1 >= dist[nx][ny][ncur]) continue;
                dist[nx][ny][ncur] = step + 1;
                d.addLast(new int[]{nx, ny, ncur});
            }
        }
        return -1;
    }
}

C++ 代码：

class Solution {
    int N = 35, K = 10, INF = 0x3f3f3f3f;
    vector<vector<vector<int>>> dist = vector<vector<vector<int>>>(N, vector<vector<int>>(N, vector<int>(1<<K, INF)));
    vector<vector<int>> dirs = {{1,0}, {-1,0}, {0,1}, {0,-1}};
public:
    int shortestPathAllKeys(vector<string>& g) {
        int n = g.size(), m = g[0].size(), cnt = 0;
        queue<vector<int>> d;
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                fill(dist[i][j].begin(), dist[i][j].end(), INF);
                char c = g[i][j];
                if (c == '@') {
                    d.push({i, j, 0});
                    dist[i][j][0] = 0;
                } else if (c >= 'a' && c <= 'z') cnt++;
            }
        }
        while (!d.empty()) {
            vector<int> info = d.front();
            d.pop();
            int x = info[0], y = info[1], cur = info[2], step = dist[x][y][cur];
            for (vector<int> di : dirs) {
                int nx = x + di[0], ny = y + di[1];
                if (nx < 0 || nx >= n || ny < 0 || ny >= m) continue;
                char c = g[nx][ny];
                if (c == '#') continue;
                if ((c >= 'A' && c <= 'Z') && (cur >> (c - 'A') & 1) == 0) continue;
                int ncur = cur;
                if (c >= 'a' && c <= 'z') ncur |= 1 << (c - 'a');
                if (ncur == (1 << cnt) - 1) return step + 1;
                if (step + 1 >= dist[nx][ny][ncur]) continue;
                dist[nx][ny][ncur] = step + 1;
                d.push({nx, ny, ncur});
            }
        }
        return -1;
    }
};

Python3 代码：

class Solution:
    def shortestPathAllKeys(self, g: List[str]) -> int:
        dirs = [[0,1], [0,-1], [1,0], [-1,0]]
        n, m, cnt = len(g), len(g[0]), 0
        dist = defaultdict(lambda : 0x3f3f3f3f)
        for i in range(n):
            for j in range(m):
                c = g[i][j]
                if c == '@':
                    d = deque([(i, j, 0)])
                    dist[(i, j, 0)] = 0
                elif 'a' <= c <= 'z':
                    cnt += 1
        while d:
            x, y, cur = d.popleft()
            step = dist[(x, y, cur)]
            for di in dirs:
                nx, ny = x + di[0], y + di[1]
                if nx < 0 or nx >= n or ny < 0 or ny >= m:
                    continue
                c = g[nx][ny]
                if c == '#':
                    continue
                if 'A' <= c <= 'Z' and (cur >> (ord(c) - ord('A')) & 1) == 0:
                    continue
                ncur = cur
                if 'a' <= c <= 'z':
                    ncur |= (1 << (ord(c) - ord('a')))
                if ncur == (1 << cnt) - 1:
                    return step + 1
                if step + 1 >= dist[(nx, ny, ncur)]:
                    continue
                dist[(nx, ny, ncur)] = step + 1
                d.append((nx, ny, ncur))
        return -1

TypeScript 代码：

function shortestPathAllKeys(g: string[]): number {
    const dirs = [[1,0],[-1,0],[0,1],[0,-1]]
    let n = g.length, m = g[0].length, cnt = 0
    const dist = new Array<Array<Array<number>>>()
    for (let i = 0; i < n; i++) {
        dist[i] = new Array<Array<number>>(m)
        for (let j = 0; j < m; j++) {
            dist[i][j] = new Array<number>(1 << 10).fill(0x3f3f3f3f)
        }
    }
    const d = []
    for (let i = 0; i < n; i++) {
        for (let j = 0; j < m; j++) {
            if (g[i][j] == '@') {
                d.push([i, j, 0]); dist[i][j][0] = 0
            } else if (g[i][j] >= 'a' && g[i][j] <= 'z') cnt++
        }
    }
    while (d.length > 0) {
        const info = d.shift()
        const x = info[0], y = info[1], cur = info[2], step = dist[x][y][cur]
        for (const di of dirs) {
            const nx = x + di[0], ny = y + di[1]
            if (nx < 0 || nx >= n || ny < 0 || ny >= m) continue
            const c = g[nx][ny]
            if (c == '#') continue
            if ('A' <= c && c <= 'Z' && ((cur >> (c.charCodeAt(0) - 'A'.charCodeAt(0)) & 1) == 0)) continue
            let ncur = cur
            if ('a' <= c && c <= 'z') ncur |= 1 << (c.charCodeAt(0) - 'a'.charCodeAt(0))
            if (ncur == (1 << cnt) - 1) return step + 1
            if (step + 1 >= dist[nx][ny][ncur]) continue
            d.push([nx, ny, ncur])
            dist[nx][ny][ncur] = step + 1
        }
    }
    return -1
}

时间复杂度：$O(n \times m \times 2^k)$
空间复杂度：$O(n \times m \times 2^k)$

最后

这是我们「刷穿 LeetCode」系列文章的第 No.864 篇，系列开始于 2021/01/01，截止于起始日 LeetCode 上共有 1916 道题目，部分是有锁题，我们将先把所有不带锁的题目刷完。

在这个系列文章里面，除了讲解解题思路以外，还会尽可能给出最为简洁的代码。如果涉及通解还会相应的代码模板。

为了方便各位同学能够电脑上进行调试和提交代码，我建立了相关的仓库：https://github.com/SharingSource/LogicStack-LeetCode 。

在仓库地址里，你可以看到系列文章的题解链接、系列文章的相应代码、LeetCode 原题链接和其他优选题解。

BFS 状态压缩

本博客所有文章除特别声明外，均采用 CC BY-SA 4.0 协议，转载请注明出处！

LC 1704. 判断字符串的两半是否相似上一篇

LC 764. 最大加号标志下一篇