LeetCode 864. 获取所有钥匙的最短路径
字数 1944 2025-12-07 00:00:11

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

题目描述
你站在一个二维的网格地图中，其中：

  • '.' 代表可以通行的空地。
  • '#' 代表墙，不能通过。
  • 小写字母（'a' 到 'f'）表示钥匙。
  • 大写字母（'A' 到 'F'）表示锁，需要对应的钥匙（小写字母）才能通过。
  • '@' 是你的起始位置。

你从起点出发，可以上下左右移动（不能移出网格）。你需要收集所有钥匙，并希望用最少的移动步数完成。返回收集所有钥匙所需的最少移动步数；如果不可能收集所有钥匙，返回 -1。

注意：

  • 钥匙数量范围是 1 到 6，分别对应 'a' 到 'f'。
  • 锁的字母与对应钥匙的字母相同（例如，锁 'A' 需要钥匙 'a'）。
  • 钥匙可以重复通过同一个格子。
  • 保证起点 '@' 是空地。

示例：

网格：["@.a.#","###.#","b.A.B"]
地图：
@ . a . #
# # # . #
b . A . B

起点是 (0,0)。钥匙是 'a' 和 'b'，锁是 'A' 和 'B'。你需要拿到钥匙 'a' 打开锁 'A'，然后拿到钥匙 'b' 打开锁 'B'。一种最短路径是：右移拿到 'a'，下移、下移、左移拿到 'b'，然后右移、上移、右移、右移通过终点。总步数是 8。

解题过程循序渐进讲解

1. 问题分析
这是一个在网格中寻找最短路径的问题，但状态不仅包括位置，还包括当前已经获得的钥匙集合，因为钥匙决定了能否通过对应的锁。因此，我们需要在状态空间中进行搜索。状态可以定义为 (x, y, keys)，其中 (x, y) 是当前位置，keys 是一个二进制掩码表示当前拥有的钥匙集合（因为钥匙最多 6 把，可以用 6 位二进制表示，每位代表对应钥匙是否已获得）。

2. 状态表示

  • 用 (x, y, mask) 表示一个状态，其中 mask 是一个整数，其二进制从低到高分别表示是否拥有钥匙 'a' 到 'f'。例如，mask = 0b000011 表示拥有钥匙 'a' 和 'b'。
  • 我们需要记录从起点到每个状态的最短步数，通常用 BFS 来保证首次到达目标状态时步数最小。

3. BFS 搜索过程

  • 起点状态为 (start_x, start_y, 0)，步数为 0。
  • 使用队列进行 BFS，同时用一个集合或哈希表记录访问过的状态 (x, y, mask) 以避免重复访问。
  • 在每一步，从队列中取出一个状态，尝试向四个方向移动：
    • 如果新位置在网格内且不是墙 '#'，则检查该位置的字符：
      • 如果是空地 '.' 或起点 '@'：直接允许移动，钥匙状态不变。
      • 如果是小写字母（钥匙）：则更新钥匙状态，将对应位置 1（new_mask = mask | (1 << (ch - 'a'))）。
      • 如果是大写字母（锁）：检查是否有对应钥匙，即 (mask >> (ch - 'A')) & 1 是否为 1，如果有则允许通过，否则不能移动。
  • 如果新状态 (new_x, new_y, new_mask) 没有被访问过，则将其加入队列，并记录步数。
  • 当 BFS 过程中遇到某个状态的钥匙集合包含了所有钥匙（即 new_mask == target_mask，其中 target_mask 是所有钥匙都拥有的掩码），则立即返回当前步数 + 1（因为从当前状态移动到新位置算一步）。

4. 详细步骤示例
以示例网格为例：

网格：["@.a.#","###.#","b.A.B"]

步骤：

  1. 扫描网格，找到起点 (0,0)，统计钥匙数量为 2（'a' 在 (0,2)，'b' 在 (2,0)）。目标掩码 target_mask = 0b11（即 3）。
  2. BFS 初始化：队列起始状态为 (0,0,0)，步数 0。
  3. 从 (0,0,0) 开始，尝试移动：
    • 向右到 (0,1)：空地，状态 (0,1,0) 入队。
    • 向下到 (1,0)：是墙 '#'，跳过。
  4. 继续 BFS 扩展。当移动到 (0,2) 时，遇到钥匙 'a'，更新掩码为 0b01。继续搜索直到获得钥匙 'b' 并打开所有锁。
  5. 当某个状态的掩码变为 0b11 时，表示已获得所有钥匙，返回当前步数。

5. 复杂度与优化

  • 网格大小最多 30x30，钥匙最多 6 把，状态总数最多 30302^6 = 57600，BFS 可在该范围内完成。
  • 使用位运算高效处理钥匙和锁的检查。

6. 边界情况

  • 没有钥匙时直接返回 0。
  • 钥匙被墙包围无法获取时返回 -1。
  • 锁和钥匙可能分布在多个区域，需通过 BFS 探索所有可能路径。

总结
本题的关键在于将钥匙持有情况作为状态的一部分，从而将问题转化为在状态空间上的最短路径搜索，通过 BFS 找到首次获得所有钥匙的状态即为最短路径。状态设计和位运算的使用是解题的核心技巧。

LeetCode 864. 获取所有钥匙的最短路径 题目描述 你站在一个二维的网格地图中，其中： '.' 代表可以通行的空地。 '#' 代表墙，不能通过。 小写字母（ 'a' 到 'f' ）表示钥匙。 大写字母（ 'A' 到 'F' ）表示锁，需要对应的钥匙（小写字母）才能通过。 '@' 是你的起始位置。 你从起点出发，可以上下左右移动（不能移出网格）。你需要收集所有钥匙，并希望用最少的移动步数完成。返回收集所有钥匙所需的最少移动步数；如果不可能收集所有钥匙，返回 -1。 注意： 钥匙数量范围是 1 到 6，分别对应 'a' 到 'f' 。 锁的字母与对应钥匙的字母相同（例如，锁 'A' 需要钥匙 'a'）。 钥匙可以重复通过同一个格子。 保证起点 '@' 是空地。 示例： 起点是 (0,0)。钥匙是 'a' 和 'b'，锁是 'A' 和 'B'。你需要拿到钥匙 'a' 打开锁 'A'，然后拿到钥匙 'b' 打开锁 'B'。一种最短路径是：右移拿到 'a'，下移、下移、左移拿到 'b'，然后右移、上移、右移、右移通过终点。总步数是 8。 解题过程循序渐进讲解 1. 问题分析 这是一个在网格中寻找最短路径的问题，但状态不仅包括位置，还包括当前已经获得的钥匙集合，因为钥匙决定了能否通过对应的锁。因此，我们需要在状态空间中进行搜索。状态可以定义为 (x, y, keys) ，其中 (x, y) 是当前位置， keys 是一个二进制掩码表示当前拥有的钥匙集合（因为钥匙最多 6 把，可以用 6 位二进制表示，每位代表对应钥匙是否已获得）。 2. 状态表示 用 (x, y, mask) 表示一个状态，其中 mask 是一个整数，其二进制从低到高分别表示是否拥有钥匙 'a' 到 'f'。例如， mask = 0b000011 表示拥有钥匙 'a' 和 'b'。 我们需要记录从起点到每个状态的最短步数，通常用 BFS 来保证首次到达目标状态时步数最小。 3. BFS 搜索过程 起点状态为 (start_x, start_y, 0) ，步数为 0。 使用队列进行 BFS，同时用一个集合或哈希表记录访问过的状态 (x, y, mask) 以避免重复访问。 在每一步，从队列中取出一个状态，尝试向四个方向移动： 如果新位置在网格内且不是墙 '#' ，则检查该位置的字符： 如果是空地 '.' 或起点 '@' ：直接允许移动，钥匙状态不变。 如果是小写字母（钥匙）：则更新钥匙状态，将对应位置 1（ new_mask = mask | (1 << (ch - 'a')) ）。 如果是大写字母（锁）：检查是否有对应钥匙，即 (mask >> (ch - 'A')) & 1 是否为 1，如果有则允许通过，否则不能移动。 如果新状态 (new_x, new_y, new_mask) 没有被访问过，则将其加入队列，并记录步数。 当 BFS 过程中遇到某个状态的钥匙集合包含了所有钥匙（即 new_mask == target_mask ，其中 target_mask 是所有钥匙都拥有的掩码），则立即返回当前步数 + 1（因为从当前状态移动到新位置算一步）。 4. 详细步骤示例 以示例网格为例： 步骤： 扫描网格，找到起点 (0,0)，统计钥匙数量为 2（'a' 在 (0,2)，'b' 在 (2,0)）。目标掩码 target_mask = 0b11 （即 3）。 BFS 初始化：队列起始状态为 (0,0,0) ，步数 0。 从 (0,0,0) 开始，尝试移动： 向右到 (0,1)：空地，状态 (0,1,0) 入队。 向下到 (1,0)：是墙 '#' ，跳过。 继续 BFS 扩展。当移动到 (0,2) 时，遇到钥匙 'a'，更新掩码为 0b01 。继续搜索直到获得钥匙 'b' 并打开所有锁。 当某个状态的掩码变为 0b11 时，表示已获得所有钥匙，返回当前步数。 5. 复杂度与优化 网格大小最多 30x30，钥匙最多 6 把，状态总数最多 30 30 2^6 = 57600，BFS 可在该范围内完成。 使用位运算高效处理钥匙和锁的检查。 6. 边界情况 没有钥匙时直接返回 0。 钥匙被墙包围无法获取时返回 -1。 锁和钥匙可能分布在多个区域，需通过 BFS 探索所有可能路径。 总结 本题的关键在于将钥匙持有情况作为状态的一部分，从而将问题转化为在状态空间上的最短路径搜索，通过 BFS 找到首次获得所有钥匙的状态即为最短路径。状态设计和位运算的使用是解题的核心技巧。