获取所有钥匙的最短路径
难度:
标签:
题目描述
给定一个二维网格 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.lengthn == grid[i].length1 <= m, n <= 30grid[i][j]只含有'.','#','@','a'-'f'以及'A'-'F'- 钥匙的数目范围是
[1, 6] - 每个钥匙都对应一个 不同 的字母
- 每个钥匙正好打开一个对应的锁
代码结果
运行时间: 139 ms, 内存: 16.7 MB
解释
方法:
这个题解采用了广度优先搜索（BFS）来找到获取所有钥匙的最短路径。首先，我们遍历整个网格以确定起点位置和所需收集的所有钥匙。每个钥匙对应一个二进制位，通过位操作来跟踪已收集的钥匙。搜索从起点开始，使用队列存储当前位置和已收集的钥匙状态。对于每个位置，我们尝试向四个方向移动，检查是否遇到墙壁、钥匙或锁。如果是钥匙，我们更新钥匙状态；如果是锁，我们检查是否已收集对应的钥匙。使用三维数组记录已访问的状态，以防止重复工作和无限循环。当收集到所有钥匙时，返回当前的步数。如果队列耗尽还未收集完所有钥匙，返回-1。
时间复杂度:
O(m * n * 2^k)
空间复杂度:
O(m * n * 2^k)
代码细节讲解
🦆
题解中提到使用三维数组来防止重复访问，具体是如何定义这个三维数组的？每个维度代表什么内容？
▷🦆
在BFS实现中，如何处理遇到锁但没有相应钥匙的情况？题解中是否有明确的跳过逻辑？
▷🦆
题解提及每个状态由坐标(x, y)和已收集的钥匙状态定义，那么在什么情况下会更新这个状态？
▷