Python 迷宫寻路算法：广度优先搜索 (BFS) 实现

以下是使用广度优先搜索算法 (BFS) 来解决迷宫寻路问题的 Python 代码实现：

from collections import deque

def bfs(maze, start, end):
    rows, cols = len(maze), len(maze[0])  # 迷宫大小
    directions = [(0, -1), (0, 1), (-1, 0), (1, 0)]  # 上、右、下、左四个方向的移动向量

    queue = deque([start])  # 初始化队列，将起始位置加入队列
    visited = set()  # 记录已访问的节点

    while queue:
        cur_pos = queue.popleft()  # 取出队列首部的节点

        if cur_pos == end:  # 如果当前位置是终点，返回路径
            path = []
            while cur_pos != start:
                path.append(cur_pos)
                cur_pos = cur_pos[2]
            path.append(start)
            path.reverse()
            return path

        visited.add(cur_pos)  # 标记当前位置已访问

        for direction in directions:  # 检查四个方向是否可以移动
            next_row = cur_pos[0] + direction[0]
            next_col = cur_pos[1] + direction[1]
            next_pos = (next_row, next_col, cur_pos)  # 记录下一个位置和当前位置的引用

            if (
                0 <= next_row < rows
                and 0 <= next_col < cols
                and maze[next_row][next_col] == 0
                and next_pos not in visited
            ):
                queue.append(next_pos)  # 将下一个位置加入队列

    return None  # 没有找到路径

maze = [
    [0, 0, 1, 0, 0],
    [0, 0, 0, 0, 0],
    [0, 0, 1, 1, 1],
    [1, 1, 0, 1, 1],
    [0, 0, 0, 0, 0],
]
start = (0, 0, None)  # 起始位置为 (0, 0)，并且没有前驱节点
end = (4, 4)  # 终点位置为 (4, 4)
print(bfs(maze, start, end))

这段代码使用了一个队列来实现广度优先搜索。首先，将起始位置加入队列，并记录访问过的节点。然后开始循环遍历队列，每次从队列中取出头部的节点。如果该节点是终点，则回溯路径并返回。否则，检查当前节点的四个相邻位置是否可达，并且尚未访问过，然后将符合条件的节点加入队列。如果遍历结束并且没有找到路径，返回 None。