Python 实现：BFS 求最短路径
关键行会在运行中高亮
from collections import deque
def bfs_shortest_path(grid, start, end):
rows, cols = len(grid), len(grid[0])
queue = deque([start]) # 队列初始化
visited = {start} # 记录已访问
parent = {start: None} # 记录父节点用于回溯
while queue: # 队列不为空则继续搜索
r, c = queue.popleft() # 取出队首元素
if (r, c) == end: # 到达终点
break
for dr, dc in [(-1,0), (1,0), (0,-1), (0,1)]:
nr, nc = r + dr, c + dc
if 0 <= nr < rows and 0 <= nc < cols:
if grid[nr][nc] != 1 and (nr, nc) not in visited:
visited.add((nr, nc))
parent[(nr, nc)] = (r, c)
queue.append((nr, nc)) # 邻居入队
# 根据 parent 字典重建最短路径
path = []
cur = end
while cur is not None:
path.append(cur)
cur = parent.get(cur)
return path[::-1] if path and path[-1] == start else []