解题思路：

状态压缩 + BFS

利用钥匙不超过6并且按字母顺序排列，我们可以使用 int 类型二进制代表当前的钥匙收集情况

若 state 的二进制中的第 k 位为 1，代表当前编号的钥匙已经被收集了，后续遇到对应的锁可以打开。

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

以上为状态压缩

使用这样的方式以后，我们就要开始 钥匙检测 和 更新钥匙收集状态 ：

  1. 钥匙检测：(state >> k) & 1 若返回 1 则说明存在编号为K的钥匙
  2. 更新钥匙收集状态：state |= 1 << k, 将state第K位设置为 1，仅代表当前更新收集到新种类的编号为K的钥匙。

接下来就是 BFS 查找过程了：

  1. 遍历一遍棋盘，查找起点 @ 并将其入队列，队列的维护是 (x, y, state) 的三元组状态, 其中x, y是位置，state为钥匙收集状态。 查找的起点的同时我们要记录钥匙的数量，并使用哈希表或者数组记录每个状态所需要消耗最少步数 step
  2. 进行四联通方向的 BFS ，转移过程中需要注意 遇到锁需要对应钥匙才能通过 & 遇到钥匙需要更新对应的state再进行入队
  3. 当 BFS 时遇到 state = (1 << cnt) - 1 时，代表所有钥匙被收集完毕，可以结束搜索。

代码：

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
45
46
class Solution:
    def shortestPathAllKeys(self, grid: List[str]) -> int:
        from collections import deque, defaultdict

        # 方向
        dirs = [[0, 1], [0, -1], [-1, 0], [1, 0]]
        # 行， 列， 钥匙数量
        n, m, cnt = len(grid), len(grid[0]), 0
        dist = defaultdict(lambda: inf)
        q = deque()
        for i in range(n):
            for j in range(m):
                c = grid[i][j]
                # 起点位置
                if c == '@':
                    q = deque([(i, j, 0)])
                    dist[(i, j, 0)] = 0
                # 钥匙数量
                elif 'a' <= c <= 'z':
                    cnt += 1

        while q:
            x, y, cur = q.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 = grid[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
                q.append((nx, ny, ncur))
        return -1