Python实现广度优先搜索（BFS）求解迷宫最短路径

广度优先搜索（BFS）是一种用于图和树的遍历算法，它从图的某一节点（源点）开始，访问离该节点最近的节点，然后逐步向外扩展，直到达到目标节点或搜索完所有可达节点。在求解迷宫最短路径问题时，我们可以将迷宫表示为一个二维数组，其中0表示可通过的路径，1表示墙壁或障碍物。使用BFS算法可以按层次顺序遍历迷宫，找到从起点到终点的最短路径。

下面是一个Python实现广度优先搜索求解迷宫最短路径的示例代码：

from collections import deque
def bfs(maze, start, end):
    # 创建一个队列并将起点入队
    queue = deque([start])
    # 创建一个字典用于记录每个位置是否已访问过
    visited = {(0, 0): True}
    # 定义四个方向的偏移量
    directions = [(0, 1), (0, -1), (1, 0), (-1, 0)]
    # 当队列不为空时循环执行以下代码块
    while queue:
        # 获取当前位置并标记为已访问
        x, y = queue.popleft()
        # 如果当前位置是终点，则返回True表示找到了最短路径
        if (x, y) == end:
            return True
        # 遍历四个方向上的相邻位置
        for dx, dy in directions:
            nx, ny = x + dx, y + dy
            # 如果相邻位置在迷宫范围内且未被访问过且不是墙壁或障碍物，则将该位置入队并标记为已访问
            if 0 <= nx < len(maze) and 0 <= ny < len(maze[0]) and (nx, ny) not in visited and maze[nx][ny] == 0:
                queue.append((nx, ny))
                visited[(nx, ny)] = True
    # 如果无法找到最短路径，则返回False
    return False

在上面的代码中，我们首先定义了一个bfs函数，它接受一个二维数组maze表示迷宫，以及起点和终点的坐标start和end。我们使用一个队列queue来按层次顺序遍历迷宫，并使用一个字典visited来记录每个位置是否已访问过。我们还定义了一个变量directions来存储四个方向的偏移量。在主循环中，我们不断从队列中取出位置并标记为已访问，然后遍历四个方向上的相邻位置。如果相邻位置在迷宫范围内且未被访问过且不是墙壁或障碍物，则将该位置入队并标记为已访问。当队列为空时，如果当前位置是终点，则返回True表示找到了最短路径；否则返回False表示无法找到最短路径。