1.题目基本信息
1.1.题目描述
给定一个二维网格 grid ，其中：
- ‘.’ 代表一个空房间
- ‘#’ 代表一堵墙
- ‘@’ 是起点
- 小写字母代表钥匙
- 大写字母代表锁
我们从起点开始出发，一次移动是指向四个基本方向之一行走一个单位空间。我们不能在网格外面行走，也无法穿过一堵墙。如果途经一个钥匙，我们就把它捡起来。除非我们手里有对应的钥匙，否则无法通过锁。
假设 k 为 钥匙/锁 的个数，且满足 1 <= k <= 6，字母表中的前 k 个字母在网格中都有自己对应的一个小写和一个大写字母。换言之，每个锁有唯一对应的钥匙，每个钥匙也有唯一对应的锁。另外，代表钥匙和锁的字母互为大小写并按字母顺序排列。
返回获取所有钥匙所需要的移动的最少次数。如果无法获取所有钥匙，返回 -1 。
1.2.题目地址
https://leetcode.cn/problems/shortest-path-to-get-all-keys/description/
2.解题方法
2.1.解题思路
BFS+字符串标记钥匙状态/二进制标记钥匙状态
2.2.解题步骤
第一步，将各个钥匙字符离散化为0,1,2…的数字
第二步，使用广度优先搜索遍历每个节点。BFS的使用队列存储遍历项，遍历的项为结构为(x坐标,y坐标,当前步数,当前已获取的钥匙的状态字符串)，同时使用visited集合存储已经访问的不可重复状态，访问项结构为(x坐标,y坐标,当前已获取的钥匙的状态字符串)；现将钥匙的状态字符串记为keys，keys[i]=”1″代表已经获取到了离散值为i的钥匙，等于”0″则代表没有获取到。这里BFS的判断是否将下一个点(nx,ny)加入到队列的逻辑相对于普通的BFS更复杂，因为当碰到钥匙时，其前面的路径上的部分点是可以重复访问的，所以的前面的visited最后加上了keys项。下面是当面对合法位置四周的位置是否加入队列的判断逻辑，记当前周围的一个待判断点为P(nx,ny)：
- 第一，需要保证P点在网格之内，同时该点不是墙，即不为”#”；
- 第二，当P位置为.或者#时，如果有和当前一样的钥匙状态遍历过，则跳过，反之加入队列进行访问，并将访问状态加入visited；
- 第三，当P点的值为大写字母，则代表是一把锁，如果当前的钥匙状态中有这把锁对应的钥匙，则可以将P点的信息加入到队列que中进行访问，并使用visited记录访问状态，反之跳过；
- 第四，当P点的值为小写字母时，代表P点为钥匙，如果添加该钥匙后，已经有的钥匙数等于所有的钥匙数，则可以直接返回路径长度，程序结束，反之，如果P点的构建的状态没有访问过，则构建P点的遍历项加入队列que进行访问，并将访问记录添加到visied中。
最后，如果遍历所有的项都没有返回一条合法的路径长度，说明不存在这么一条路径，返回-1。
3.解题代码
Python代码（字符串标记钥匙状态）
from collections import deque
class Solution:
# BFS+字符串标记钥匙状态
def shortestPathAllKeys(self, grid: List[str]) -> int:
directions=[[-1,0],[0,-1],[1,0],[0,1]]
rows,cols=len(grid),len(grid[0])
# 第一步，将各个钥匙字符离散化为0,1,2...的数字
sx,sy=0,0
key2IndexMap={}
for i in range(rows):
for j in range(cols):
if grid[i][j]=="@":
sx,sy=i,j
elif grid[i][j].islower():
key2IndexMap[grid[i][j]]=len(key2IndexMap)
# print(key2IndexMap)
# 第二步，使用广度优先搜索遍历每个节点。BFS的使用队列存储遍历项，遍历的项为结构为(x坐标,y坐标,当前步数,当前已获取的钥匙的状态字符串)，同时使用visited集合存储已经访问的不可重复状态，访问项结构为(x坐标,y坐标,当前已获取的钥匙的状态字符串)；现将钥匙的状态字符串记为keys，keys[i]="1"代表已经获取到了离散值为i的钥匙，等于"0"则代表没有获取到。这里BFS的判断是否将下一个点(nx,ny)加入到队列的逻辑相对于普通的BFS更复杂，因为当碰到钥匙时，其前面的路径上的部分点是可以重复访问的，所以的前面的visited最后加上了keys项。下面是当面对合法位置四周的位置是否加入队列的判断逻辑，记当前周围的一个待判断点为P(nx,ny)：第一，需要保证P点在网格之内，同时该点不是墙，即不为"#"；第二，当P位置为.或者#时，如果有和当前一样的钥匙状态遍历过，则跳过，反之加入队列进行访问，并将访问状态加入visited；第三，当P点的值为大写字母，则代表是一把锁，如果当前的钥匙状态中有这把锁对应的钥匙，则可以将P点的信息加入到队列que中进行访问，并使用visited记录访问状态，反之跳过；第四，当P点的值为小写字母时，代表P点为钥匙，如果添加该钥匙后，已经有的钥匙数等于所有的钥匙数，则可以直接返回路径长度，程序结束，反之，如果P点的构建的状态没有访问过，则构建P点的遍历项加入队列que进行访问，并将访问记录添加到visied中。最后，如果遍历所有的项都没有返回一条合法的路径长度，说明不存在这么一条路径，返回-1。
defaultKeys="0"*len(key2IndexMap) # 字符串存储状态
que=deque([(sx,sy,0,defaultKeys)])
visited=set()
while que:
for i in range(len(que)):
x,y,steps,oriKeys=que.popleft()
for dx,dy in directions:
keys=oriKeys
nx,ny=x+dx,y+dy
if 0<=nx<rows and 0<=ny<cols and grid[nx][ny]!="#":
if grid[nx][ny] == "." or grid[nx][ny] == "@":
# 没有参观的.和@能访问
# print((nx,ny,steps+1,keys))
if (nx,ny,keys) not in visited:
que.append((nx,ny,steps+1,keys))
visited.add((nx,ny,keys))
elif grid[nx][ny].islower():
# 如果没有这个钥匙，则访问
keyIndex=key2IndexMap[grid[nx][ny]]
# print((nx,ny,steps+1,keys))
keys=keys[:keyIndex]+"1"+keys[keyIndex+1:]
if (nx,ny,keys) not in visited:
if keys=="1"*len(key2IndexMap):
return steps+1
que.append((nx,ny,steps+1,keys))
visited.add((nx,ny,keys))
else: # 大写字母，表示是把锁
# 如果这把锁没访问过且有对应的钥匙，则可以访问
# print((nx,ny,steps+1,keys))
matchKeyIndex=key2IndexMap[grid[nx][ny].lower()]
if (nx,ny,keys) not in visited and keys[matchKeyIndex]=="1":
que.append((nx,ny,steps+1,keys))
visited.add((nx,ny,keys))
# print()
return -1
Python代码（二进制标记钥匙状态）
from collections import deque
class Solution:
# BFS+二进制标记钥匙状态
def shortestPathAllKeys(self, grid: List[str]) -> int:
directions=[[-1,0],[0,-1],[1,0],[0,1]]
rows,cols=len(grid),len(grid[0])
sx,sy=0,0
key2IndexMap={}
for i in range(rows):
for j in range(cols):
if grid[i][j]=="@":
sx,sy=i,j
elif grid[i][j].islower():
key2IndexMap[grid[i][j]]=len(key2IndexMap)
# print(key2IndexMap)
defaultKeys=0 # 二进制存储状态
que=deque([(sx,sy,0,defaultKeys)])
visited=set()
while que:
for i in range(len(que)):
x,y,steps,oriKeys=que.popleft()
for dx,dy in directions:
keys=oriKeys
nx,ny=x+dx,y+dy
if 0<=nx<rows and 0<=ny<cols and grid[nx][ny]!="#":
if grid[nx][ny] == "." or grid[nx][ny] == "@":
# 没有参观的.和@能访问
# print((nx,ny,steps+1,keys))
if (nx,ny,keys) not in visited:
que.append((nx,ny,steps+1,keys))
visited.add((nx,ny,keys))
elif grid[nx][ny].islower():
# 如果没有这个钥匙，则访问
keyIndex=key2IndexMap[grid[nx][ny]]
# print((nx,ny,steps+1,keys))
keys=keys|(1<<keyIndex)
if (nx,ny,keys) not in visited:
if keys==(1<<len(key2IndexMap))-1:
return steps+1
que.append((nx,ny,steps+1,keys))
visited.add((nx,ny,keys))
else: # 大写字母，表示是把锁
# 如果这把锁没访问过且有对应的钥匙，则可以访问
# print((nx,ny,steps+1,keys))
matchKeyIndex=key2IndexMap[grid[nx][ny].lower()]
if (nx,ny,keys) not in visited and keys&(1<<matchKeyIndex):
que.append((nx,ny,steps+1,keys))
visited.add((nx,ny,keys))
# print()
return -1
4.执行结果
