如何使用BFS重建二维迷宫的路径以找到最短路径

from collections import deque

def find_shortest_path(maze, start, end):
    # 迷宫的行数和列数
    rows, cols = len(maze), len(maze[0])

    # 定义四个方向的偏移量，用于计算相邻格子的坐标
    directions = [(-1, 0), (1, 0), (0, -1), (0, 1)]

    # 创建队列并加入起点
    queue = deque()
    queue.append(start)

    # 创建visited数组并初始化为False
    visited = [[False] * cols for _ in range(rows)]
    visited[start[0]][start[1]] = True

    # 创建prev数组用于记录路径
    prev = [[None] * cols for _ in range(rows)]

    while queue:
        x, y = queue.popleft()
        if (x, y) == end:
            break

        for dx, dy in directions:
            new_x, new_y = x + dx, y + dy
            if 0 <= new_x < rows and 0 <= new_y < cols and not visited[new_x][new_y] and maze[new_x][new_y] != '#':
                queue.append((new_x, new_y))
                visited[new_x][new_y] = True
                prev[new_x][new_y] = (x, y)

    # 重建最短路径
    path = []
    x, y = end
    while (x, y) != start:
        path.append((x, y))
        x, y = prev[x][y]
    path.append(start)
    path.reverse()

    return path

# 示例迷宫
maze = [
    ['S', '.', '.', '#', '.', '.', '.'],
    ['.', '#', '.', '.', '.', '#', '.'],
    ['.', '#', '.', '.', '.', '.', '.'],
    ['.', '.', '#', '#', '.', '.', '.'],
    ['#', '.', '#', 'E', '.', '#', '.']
]

start = (0, 0)
end = (4, 3)

shortest_path = find_shortest_path(maze, start, end)
print(shortest_path)