获取所有钥匙的最短路径

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

难度: Hard

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

Submission

运行时间: 139 ms

内存: 16.7 MB

class Solution:
    def shortestPathAllKeys(self, grid: List[str]) -> int:
        m, n = len(grid), len(grid[0])
        q = []  # queue for BFS
        keys_to_find = 0  # number of keys to find
        for i in range(m):
            for j in range(n):
                if grid[i][j] == "@":
                    # Start position and initial keys bitmask
                    q.append((i, j, 0))
                elif grid[i][j].islower():
                    # count the number of keys we need to collect
                    keys_to_find |= 1 << (ord(grid[i][j]) - ord('a'))

        dirc = [(1, 0), (-1, 0), (0, 1), (0, -1)]
        seen = [[[False] * (1 << 6) for _ in range(n)] for _ in range(m)]
        step = 0  # number of steps taken

        while q:
            size = len(q)
            for _ in range(size):
                x, y, collected_keys = q.pop(0)
                if collected_keys == keys_to_find:
                    return step
                for dx, dy in dirc:
                    nx, ny = x + dx, y + dy
                    if 0 <= nx < m and 0 <= ny < n:
                        cell = grid[nx][ny]
                        if cell == "#":  # Wall
                            continue
                        elif cell.islower():  # Key
                            new_collected_keys = collected_keys | (1 << (ord(cell) - ord('a')))
                        else:
                            new_collected_keys = collected_keys
                        
                        if cell.isupper() and not (new_collected_keys & (1 << (ord(cell.lower()) - ord('a')))):
                            continue  # Don't have the key for this lock

                        if not seen[nx][ny][new_collected_keys]:
                            seen[nx][ny][new_collected_keys] = True
                            q.append((nx, ny, new_collected_keys))
            step += 1

        return -1  # Impossible to collect all keys

Explain

这个题解采用了广度优先搜索（BFS）来找到获取所有钥匙的最短路径。首先，我们遍历整个网格以确定起点位置和所需收集的所有钥匙。每个钥匙对应一个二进制位，通过位操作来跟踪已收集的钥匙。搜索从起点开始，使用队列存储当前位置和已收集的钥匙状态。对于每个位置，我们尝试向四个方向移动，检查是否遇到墙壁、钥匙或锁。如果是钥匙，我们更新钥匙状态；如果是锁，我们检查是否已收集对应的钥匙。使用三维数组记录已访问的状态，以防止重复工作和无限循环。当收集到所有钥匙时，返回当前的步数。如果队列耗尽还未收集完所有钥匙，返回-1。

时间复杂度: O(m * n * 2^k)

空间复杂度: O(m * n * 2^k)

class Solution:
    def shortestPathAllKeys(self, grid: List[str]) -> int:
        m, n = len(grid), len(grid[0])
        q = []  # BFS 队列
        keys_to_find = 0  # 要找的钥匙的二进制表示
        for i in range(m):
            for j in range(n):
                if grid[i][j] == '@':
                    q.append((i, j, 0))  # 起始位置及初始钥匙状态
                elif grid[i][j].islower():
                    keys_to_find |= 1 << (ord(grid[i][j]) - ord('a'))  # 统计所有钥匙
        dirc = [(1, 0), (-1, 0), (0, 1), (0, -1)]  # 四个方向
        seen = [[[False] * (1 << 6) for _ in range(n)] for _ in range(m)]  # 访问状态记录
        step = 0  # 步数计数
        while q:
            size = len(q)
            for _ in range(size):
                x, y, collected_keys = q.pop(0)
                if collected_keys == keys_to_find:
                    return step  # 找到所有钥匙
                for dx, dy in dirc:
                    nx, ny = x + dx, y + dy
                    if 0 <= nx < m and 0 <= ny < n:
                        cell = grid[nx][ny]
                        if cell == '#':  # 墙
                            continue
                        elif cell.islower():  # 钥匙
                            new_collected_keys = collected_keys | (1 << (ord(cell) - ord('a')))
                        else:
                            new_collected_keys = collected_keys
                        if cell.isupper() and not (new_collected_keys & (1 << (ord(cell.lower()) - ord('a')))):
                            continue  # 没有对应的钥匙
                        if not seen[nx][ny][new_collected_keys]:
                            seen[nx][ny][new_collected_keys] = True
                            q.append((nx, ny, new_collected_keys))
            step += 1
        return -1  # 如果无法收集所有钥匙

Explore

在题解中，三维数组`seen`用于记录访问状态，以避免重复访问和无限循环。这个数组的定义为`seen = [[[False] * (1 << 6) for _ in range(n)] for _ in range(m)]`。其中，第一维和第二维代表网格的行和列，即格子的位置坐标(x, y)。第三维表示钥匙的收集状态，它的大小是`1 << 6`，假设有最多6把钥匙，每一位代表一把钥匙是否已经被收集。例如，如果收集了第一把和第三把钥匙，对应的状态值将是`000101`（二进制）。总之，这个三维数组记录了在特定位置和特定钥匙收集状态下是否被访问过。

题解中确实包含处理锁的逻辑。当BFS遍历到一个锁（大写字母）时，会检查是否已收集对应的钥匙。这是通过检查当前收集的钥匙状态`new_collected_keys`中相应的位是否为1来实现的。具体操作是`new_collected_keys & (1 << (ord(cell.lower()) - ord('a')))`，其中`cell`是锁对应的字符。如果结果为假，说明没有对应的钥匙，因此会跳过当前这个位置的进一步探索。如果结果为真，说明已有对应钥匙，可以继续探索。这种逻辑有效防止进入没有钥匙的锁的位置，从而避免无效的路径探索。

状态更新发生在BFS过程中，当且仅当探索到新的位置或收集到新的钥匙时。具体来说，如果当前位置是一把未收集的钥匙，将更新钥匙状态`new_collected_keys`。此外，如果当前位置可以进一步探索（即不是墙壁，并且在有锁的情况下有对应的钥匙），则会检查这个新位置和新钥匙状态的组合是否之前访问过。如果未访问过，将该状态添加到队列中并标记为已访问。这样确保了每个有效的位置和钥匙状态组合只被探索一次，避免了不必要的重复工作和可能的无限循环。