Problem: 864. 获取所有钥匙的最短路径
思路
首先，这道题的目的是要找到所有钥匙【意味着要对找钥匙情况进行标记】 因为要找的是最短途径，所有选择使用BFS 重点是要找到所有钥匙的最小路径，其实官方也并没有给出很好的办法，这个方法很暴力，就是广度优先便利所有的节点，并把每一个新的结果存储到字典中。
解题方法
钥匙的标记方法： 找钥匙的情况可以用二级制数字curr_keys表示，例如，有4个钥匙，全找到curr_keys就是0b1111，只找到了第二个就是0b0010。 搜索方法： 广度优先搜索，对每个点【注意这里的点包含了搜索时的状态】用x,y,curr_keys三个部分表示，x,y是坐标，curr_keys表示当前寻找钥匙情况。
数据结构
dirs = [(-1, 0), (1, 0), (0, -1), (0, 1)] # 表示方向
key_to_idx = dict() # 钥匙对应的编号，例如a-->0
q = deque([(sx, sy, curr_keys)]) # 队列中sx和sy表示位置，第三位表示curr_keys的情况
dist = dict()
dist[(x, y, curr_keys)] = l # 表示当前curr_keys状态下的位置（x,y)到出发点的距离为l
复杂度
- 时间复杂度:
$O(mn*2^k)$
- 空间复杂度:
$O(mn*2^k)$
Code
class Solution:
def shortestPathAllKeys(self, grid: List[str]) -> int:
dirs = [(-1, 0), (1, 0), (0, -1), (0, 1)] # 表示方向
m, n = len(grid), len(grid[0])
sx = sy = 0 # 开始位置
key_to_idx = dict() # 钥匙对应的编号
for i in range(m):
for j in range(n):
if grid[i][j].islower():
idx = len(key_to_idx)
key_to_idx[grid[i][j]] = idx
elif grid[i][j] == "@":
sx, sy = i, j
key_num = len(key_to_idx)
q = deque([(sx, sy, 0)]) # 队列中sx和sy表示位置，第三位表示curr_keys的情况
dist = dict()
dist[(sx, sy, 0)] = 0
while q:
x, y, curr_keys = q.popleft() # curr_keys表示当前收集钥匙情况(1有0无),curr_keys == 1<<key_num-1时表示找到了所有钥匙
for tx, ty in dirs:
nx, ny = x + tx, y + ty
if 0 <= nx < m and 0 <= ny < n and grid[nx][ny] != "#":
if grid[nx][ny] == "." or (nx, ny) == (sx, sy):
if (nx, ny, curr_keys) not in dist:
dist[(nx, ny, curr_keys)] = dist[(x, y, curr_keys)] + 1
q.append((nx, ny, curr_keys))
"""为什么不用考虑原来的dist[(nx,ny,curr_keys)]的值比新的值大呢？--因为是广度优先呀！"""
elif grid[nx][ny].islower():
idx = 1 << key_to_idx[grid[nx][ny]]
if curr_keys & idx == 0:
new_curr_keys = idx | curr_keys
if new_curr_keys == (1 << key_num) - 1:
return dist[(x, y, curr_keys)] + 1
"""注意：curr_keys会改变的，要考虑钥匙虽然之前已经拿到了，但是现在的curr_keys已经更新了的情况！
所以就不能把下面的这个if语句直接写到上面的if语句里面！"""
if (nx, ny, idx | curr_keys) not in dist:
dist[(nx, ny, idx | curr_keys)] = (
dist[(x, y, curr_keys)] + 1
)
q.append((nx, ny, idx | curr_keys))
else:
idx = 1 << key_to_idx[grid[nx][ny].lower()]
if curr_keys & idx:
if (nx, ny, curr_keys) not in dist:
dist[(nx, ny, curr_keys)] = dist[(x, y, curr_keys)] + 1
q.append((nx, ny, curr_keys))
return -1
