How does bit manipulation help in Shortest Path to Get All Keys?

Each key is represented as a bit in an integer, allowing efficient checks and updates for collected keys, crucial for BFS state tracking.

What happens if a key is behind a lock?

You cannot pass through the lock until the corresponding key is collected, so BFS must explore alternative paths until the key is obtained.

Can we revisit a cell after picking up keys?

Yes, revisiting is allowed but must consider the current key bitmask to avoid redundant exploration of already visited states.

What is the maximum number of keys supported?

The problem restricts keys to a maximum of 6, which fits within a 6-bit integer for efficient bitmask representation.

Why BFS is preferred over DFS for this problem?

BFS ensures the minimum steps are found first, whereas DFS might explore longer paths and fail to guarantee the shortest path to collect all keys.

#864

Hard

auto_awesome图·搜索

LeetCode 题解工作台

获取所有钥匙的最短路径

给定一个二维网格 grid ，其中： '.' 代表一个空房间 '#' 代表一堵墙 '@' 是起点小写字母代表钥匙大写字母代表锁我们从起点开始出发，一次移动是指向四个基本方向之一行走一个单位空间。我们不能在网格外面行走，也无法穿过一堵墙。如果途经一个钥匙，我们就把它捡起来。除非我们手里有对应的钥…

数组位运算广度优先搜索矩阵

题目描述

给定一个二维网格 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]
每个钥匙都对应一个不同的字母
每个钥匙正好打开一个对应的锁

lightbulb

解题思路

方法一：状态压缩 + BFS

根据题意，我们需要从起点出发，往上下左右四个方向走，获取所有钥匙，最后返回获取所有钥匙所需要的移动的最少次数。若无法获取所有钥匙，返回 $-1$ 。

首先，我们遍历二维网格，找到起点位置 $(si, sj)$ ，并统计钥匙的个数 $k$ 。

然后，我们可以使用广度优先搜索 $BFS$ 来解决本题。由于钥匙的个数范围是 $[1, 6]$ ，我们可以用一个二进制数来表示钥匙的状态，其中第 $i$ 位为 $1$ 表示第 $i$ 把钥匙已经获取到了，为 $0$ 表示第 $i$ 把钥匙还没有获取到。

比如，以下例子中，共有 $4$ 个二进制位为 $1$ ，也就表示有 'b', 'c', 'd', 'f' $4$ 把钥匙已经获取到了。

1 0 1 1 1 0
^   ^ ^ ^
f   d c b

我们定义一个队列 $q$ 来存储当前位置以及当前拥有的钥匙的状态，即 $(i, j, \textit{state})$ ，其中 $(i, j)$ 表示当前位置， $\textit{state}$ 表示当前拥有的钥匙的状态，即 $\textit{state}$ 的第 $i$ 位为 $1$ 表示当前拥有第 $i$ 把钥匙，否则表示当前没有第 $i$ 把钥匙。

另外，定义哈希表或数组 $vis$ 记录当前位置以及当前拥有的钥匙的状态是否已经被访问过，如果访问过，则不需要再次访问。 $vis[i][j][\textit{state}]$ 表示当前位置为 $(i, j)$ ，当前拥有的钥匙的状态为 $state$ 时，是否已经被访问过。

我们从起点 $(si, sj)$ 出发，将其加入队列 $q$ ，并将 $vis[si][sj][0]$ 置为 $true$ ，表示起点位置以及拥有的钥匙的状态为 $0$ 时已经被访问过。

在广度优先搜索的过程中，我们每次从队首取出一个位置 $(i, j, \textit{state})$ ，并判断当前位置是否为终点，即当前位置是否拥有所有的钥匙，即 $state$ 的二进制表示中的 $1$ 的个数是否为 $k$ 。如果是，将当前步数作为答案返回。

否则，我们从当前位置出发，往上下左右四个方向走，如果可以走到下一个位置 $(x, y)$ ，则将 $(x, y, nxt)$ 加入队列 $q$ ，其中 $nxt$ 表示下一个位置的钥匙的状态。

这里 $(x, y)$ 首先需要满足在网格范围内，即 $0 \leq x < m$ 且 $0 \leq y < n$ 。其次，如果 $(x, y)$ 位置是墙壁，即 grid[x][y] == '#'，或者 $(x, y)$ 位置是锁，但我们没有对应的钥匙，即 grid[x][y] >= 'A' && grid[x][y] <= 'F' && (state >> (grid[x][y] - 'A') & 1) == 0)，则不能走到位置 $(x, y)$ 。否则，我们可以走到位置 $(x, y)$ 。

搜索结束，没能找到所有的钥匙，返回 $-1$ 。

时间复杂度 $O(m\times n\times 2^k)$ ，空间复杂度 $O(m\times n\times 2^k)$ 。其中 $m$ 和 $n$ 分别为网格的行数和列数，而 $k$ 为钥匙的个数。

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

class Solution:
    def shortestPathAllKeys(self, grid: List[str]) -> int:
        m, n = len(grid), len(grid[0])
        # 找起点 (si, sj)
        si, sj = next((i, j) for i in range(m) for j in range(n) if grid[i][j] == '@')
        # 统计钥匙数量
        k = sum(v.islower() for row in grid for v in row)
        dirs = (-1, 0, 1, 0, -1)
        q = deque([(si, sj, 0)])
        vis = {(si, sj, 0)}
        ans = 0
        while q:
            for _ in range(len(q)):
                i, j, state = q.popleft()
                # 找到所有钥匙，返回当前步数
                if state == (1 << k) - 1:
                    return ans

                # 往四个方向搜索
                for a, b in pairwise(dirs):
                    x, y = i + a, j + b
                    nxt = state
                    # 在边界范围内
                    if 0 <= x < m and 0 <= y < n:
                        c = grid[x][y]
                        # 是墙，或者是锁，但此时没有对应的钥匙，无法通过
                        if (
                            c == '#'
                            or c.isupper()
                            and (state & (1 << (ord(c) - ord('A')))) == 0
                        ):
                            continue
                        # 是钥匙
                        if c.islower():
                            # 更新状态
                            nxt |= 1 << (ord(c) - ord('a'))
                        # 此状态未访问过，入队
                        if (x, y, nxt) not in vis:
                            vis.add((x, y, nxt))
                            q.append((x, y, nxt))
            # 步数加一
            ans += 1
        return -1

speed

复杂度分析

指标	值
时间	complexity is O(RC(2^A + 1) + E log N) due to BFS across R*C positions with up to 2^A key combinations, where A is number of keys. Space complexity is O(N) for storing visited states for each position and key bitmask.
空间	O(\mathcal{N})

psychology

面试官常问的追问

外企场景

question_mark
Expect questions on BFS combined with bitmasking for state representation.
question_mark
Watch for cases where multiple paths reach the same cell with different keys.
question_mark
Clarify handling of unreachable keys due to locked doors blocking all paths.

warning

常见陷阱

外企场景

error
Forgetting to include the current key state in the visited set, causing cycles or incorrect answers.
error
Trying to brute-force paths without pruning, leading to exponential time explosion.
error
Incorrectly assuming keys can be collected in any order without considering locks.

swap_horiz

进阶变体

外企场景

arrow_right_alt
Grid sizes larger than 30x30 with more keys and locks to stress BFS efficiency.
arrow_right_alt
Grids where some keys are completely inaccessible unless others are collected first.
arrow_right_alt
Variants with multiple starting points requiring coordinated key collection.

help

常见问题

外企场景

继续练习

#1284 转化为全零矩阵的最少反转次数 #861 翻转矩阵后的得分 #832 翻转图像