LeetCode 864. 获取所有钥匙的最短路径
字数 2232 2025-12-22 07:54:10

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

题目描述
你从起点(0,0)出发，在一个网格迷宫中寻找所有钥匙。迷宫是一个二维网格，其中：

  • '.' 表示可以通行的空地
  • '#' 表示墙，不可通行
  • 小写字母（'a'到'f'）表示钥匙
  • 对应的大写字母（'A'到'F'）表示锁，只有持有对应的钥匙才能通过
  • '@' 表示起点位置

你需要收集所有钥匙（题目保证至少有一把钥匙，且总钥匙数K不超过6），并返回收集所有钥匙所需的最短路径步数。如果无法收集所有钥匙，返回-1。

示例
输入：grid = ["@.a..","###.#","b.A.B"]
解释：网格中有一把钥匙'a'，对应的锁'A'，以及另一把钥匙'b'。起点在左上角。
输出：8（收集所有钥匙的最短路径需要8步）

解题思路详解

这个问题本质上是一个状态空间搜索问题。在迷宫中移动时，你不仅需要记录位置(x,y)，还需要记录当前已经收集到的钥匙集合，因为不同的钥匙持有状态会影响你能否通过锁。由于钥匙最多只有6把，我们可以用一个二进制位掩码（bitmask）来表示钥匙收集状态，这样状态总数是有限的，可以用广度优先搜索（BFS） 来寻找最短路径。

步骤1：理解状态表示

  1. 位置：当前在网格中的坐标(x, y)。
  2. 钥匙持有状态：用一个整数keys的二进制位表示。例如，如果一共有3把钥匙a, b, c，那么：
    • 第0位表示钥匙'a'
    • 第1位表示钥匙'b'
    • 第2位表示钥匙'c'
    • 如果keys = 5（二进制101），表示持有钥匙'a'和'c'，没有'b'。

因此，整个搜索状态可以表示为一个三元组：(x, y, keys)。

步骤2：确定目标状态

假设总共有K把钥匙，那么当keys的二进制表示中低K位全为1时，表示收集了所有钥匙。即目标状态是keys == (1 << K) - 1。

步骤3：BFS搜索设计

  1. 队列：存放待探索的状态(x, y, keys)，同时记录步数。
  2. 访问标记：用一个三维数组visited[x][y][keys]记录某个状态是否已经访问过，避免重复探索。
  3. 初始状态：找到起点'@'的位置，初始keys=0，步数为0。
  4. 状态转移：从当前状态(x, y, keys)可以向上下左右四个方向移动，得到新位置(nx, ny)：
    • 如果新位置越界或是'#'，跳过。
    • 如果新位置是锁（大写字母），检查是否有对应钥匙：
      锁'A'对应钥匙'a'（第0位），锁'B'对应钥匙'b'（第1位），依此类推。
      如果(keys >> (ch - 'A')) & 1 == 1，表示有钥匙，可以通行；否则跳过。
    • 如果新位置是钥匙（小写字母），更新钥匙状态：
      new_keys = keys | (1 << (ch - 'a'))。
    • 其他情况（空地'.'或起点'@'），钥匙状态不变。
  5. 如果新状态(nx, ny, new_keys)没有被访问过，将其加入队列，并标记已访问。
  6. 如果new_keys等于目标钥匙掩码，则当前步数+1即为答案（因为到达该格子时步数还没+1，需要加上移动的这一步）。

步骤4：具体例子走一遍

以示例grid = ["@.a..","###.#","b.A.B"]为例：

  1. 钥匙：'a'（索引0）、'b'（索引1），总钥匙数K=2，目标keys = 11（二进制3）。
  2. 起点(0,0)，状态(0,0,0)。
  3. BFS过程（简化）：
    • 从(0,0,0)可以走到(0,1,0)（空位）。
    • 继续走到(0,2,0)遇到钥匙'a'，更新状态为(0,2,1)（二进制01，表示有钥匙a）。
    • 从(0,2,1)可以走回头路吗？可以，但visited会避免重复。
    • 关键：要从(0,2,1)去拿钥匙'b'，需要先通过锁'A'。锁'A'在(2,2)，检查钥匙a（第0位）是否持有：(1 >> 0) & 1 = 1，可以通过。
    • 通过锁'A'后到达(2,3,1)，再走到(2,4,1)拿到钥匙'b'，更新状态为(2,4,3)（二进制11，表示有钥匙a和b），此时钥匙全收集，返回步数。

计算最短路径为8步。

步骤5：算法复杂度

  • 网格大小：m x n
  • 钥匙状态数：2^K（K≤6，最多64种状态）
  • 总状态数：m * n * 2^K，每个状态最多扩展4个方向。
  • 时间复杂度：O(m * n * 2^K)，在本题约束下是可接受的。

步骤6：实现注意事项

  1. 先遍历一次网格，找到起点位置和总钥匙数K。
  2. 用队列实现BFS，每个队列元素可以存储(x, y, keys, step)，也可以将步数单独用数组记录。
  3. 访问数组visited[m][n][1<<K]需要根据网格大小和K动态创建（注意内存）。
  4. 方向数组dirs = [(0,1),(0,-1),(1,0),(-1,0)]。

总结
本题的关键在于将“钥匙持有情况”纳入BFS的状态中，从而将问题转化为一个分层图的最短路径问题。通过位运算高效地表示和更新钥匙集合，使得BFS可以在有限的状态空间中搜索到最优解。

LeetCode 864. 获取所有钥匙的最短路径 题目描述 你从起点 (0,0) 出发，在一个网格迷宫中寻找所有钥匙。迷宫是一个二维网格，其中： '.' 表示可以通行的空地 '#' 表示墙，不可通行 小写字母（ 'a' 到 'f' ）表示钥匙 对应的大写字母（ 'A' 到 'F' ）表示锁，只有持有对应的钥匙才能通过 '@' 表示起点位置 你需要收集所有钥匙（题目保证至少有一把钥匙，且总钥匙数 K 不超过6），并返回收集所有钥匙所需的最短路径步数。如果无法收集所有钥匙，返回 -1 。 示例 输入： grid = ["@.a..","###.#","b.A.B"] 解释：网格中有一把钥匙 'a' ，对应的锁 'A' ，以及另一把钥匙 'b' 。起点在左上角。 输出： 8 （收集所有钥匙的最短路径需要8步） 解题思路详解 这个问题本质上是一个 状态空间搜索 问题。在迷宫中移动时，你不仅需要记录位置 (x,y) ，还需要记录当前已经收集到的钥匙集合，因为不同的钥匙持有状态会影响你能否通过锁。由于钥匙最多只有6把，我们可以用一个 二进制位掩码 （bitmask）来表示钥匙收集状态，这样状态总数是有限的，可以用 广度优先搜索（BFS） 来寻找最短路径。 步骤1：理解状态表示 位置 ：当前在网格中的坐标 (x, y) 。 钥匙持有状态 ：用一个整数 keys 的二进制位表示。例如，如果一共有3把钥匙 a, b, c ，那么： 第0位表示钥匙 'a' 第1位表示钥匙 'b' 第2位表示钥匙 'c' 如果 keys = 5 （二进制 101 ），表示持有钥匙 'a' 和 'c' ，没有 'b' 。 因此，整个搜索状态可以表示为一个三元组： (x, y, keys) 。 步骤2：确定目标状态 假设总共有 K 把钥匙，那么当 keys 的二进制表示中低 K 位全为 1 时，表示收集了所有钥匙。即目标状态是 keys == (1 << K) - 1 。 步骤3：BFS搜索设计 队列 ：存放待探索的状态 (x, y, keys) ，同时记录步数。 访问标记 ：用一个三维数组 visited[x][y][keys] 记录某个状态是否已经访问过，避免重复探索。 初始状态 ：找到起点 '@' 的位置，初始 keys=0 ，步数为0。 状态转移 ：从当前状态 (x, y, keys) 可以向上下左右四个方向移动，得到新位置 (nx, ny) ： 如果新位置越界或是 '#' ，跳过。 如果新位置是锁（大写字母），检查是否有对应钥匙： 锁 'A' 对应钥匙 'a' （第0位），锁 'B' 对应钥匙 'b' （第1位），依此类推。 如果 (keys >> (ch - 'A')) & 1 == 1 ，表示有钥匙，可以通行；否则跳过。 如果新位置是钥匙（小写字母），更新钥匙状态： new_keys = keys | (1 << (ch - 'a')) 。 其他情况（空地 '.' 或起点 '@' ），钥匙状态不变。 如果新状态 (nx, ny, new_keys) 没有被访问过，将其加入队列，并标记已访问。 如果 new_keys 等于目标钥匙掩码，则当前步数+1即为答案（因为到达该格子时步数还没+1，需要加上移动的这一步）。 步骤4：具体例子走一遍 以示例 grid = ["@.a..","###.#","b.A.B"] 为例： 钥匙： 'a' （索引0）、 'b' （索引1），总钥匙数 K=2 ，目标 keys = 11 （二进制 3 ）。 起点 (0,0) ，状态 (0,0,0) 。 BFS过程（简化）： 从 (0,0,0) 可以走到 (0,1,0) （空位）。 继续走到 (0,2,0) 遇到钥匙 'a' ，更新状态为 (0,2,1) （二进制 01 ，表示有钥匙 a ）。 从 (0,2,1) 可以走回头路吗？可以，但 visited 会避免重复。 关键：要从 (0,2,1) 去拿钥匙 'b' ，需要先通过锁 'A' 。锁 'A' 在 (2,2) ，检查钥匙 a （第0位）是否持有： (1 >> 0) & 1 = 1 ，可以通过。 通过锁 'A' 后到达 (2,3,1) ，再走到 (2,4,1) 拿到钥匙 'b' ，更新状态为 (2,4,3) （二进制 11 ，表示有钥匙 a 和 b ），此时钥匙全收集，返回步数。 计算最短路径为8步。 步骤5：算法复杂度 网格大小： m x n 钥匙状态数： 2^K （K≤6，最多64种状态） 总状态数： m * n * 2^K ，每个状态最多扩展4个方向。 时间复杂度： O(m * n * 2^K) ，在本题约束下是可接受的。 步骤6：实现注意事项 先遍历一次网格，找到起点位置和总钥匙数 K 。 用队列实现BFS，每个队列元素可以存储 (x, y, keys, step) ，也可以将步数单独用数组记录。 访问数组 visited[m][n][1<<K] 需要根据网格大小和K动态创建（注意内存）。 方向数组 dirs = [(0,1),(0,-1),(1,0),(-1,0)] 。 总结 本题的关键在于将“钥匙持有情况”纳入BFS的状态中，从而将问题转化为一个 分层图的最短路径问题 。通过位运算高效地表示和更新钥匙集合，使得BFS可以在有限的状态空间中搜索到最优解。