用BFS算法实现迷宫问题

迷宫问题是经典的搜索问题，其中一个常用的解法是BFS算法（广度优先搜索）。

BFS算法的基本思想是从起点开始，依次将每个可达的节点加入队列中，然后逐个出队进行拓展，直到找到终点或队列为空。

以下是BFS算法实现迷宫问题的示例代码：

from collections import deque

def bfs(maze, start, end):
    queue = deque([start])  # 将起点加入队列
    visited = set([start])  # 标记起点已被访问过
    
    while queue:
        x, y = queue.popleft()  # 取出队列中的第一个点
        if (x, y) == end:
            return True  # 找到终点，返回True
        for dx, dy in [(0, 1), (0, -1), (1, 0), (-1, 0)]:  # 上下左右四个方向
            nx, ny = x + dx, y + dy
            if 0 <= nx < len(maze) and 0 <= ny < len(maze[0]) and maze[nx][ny] == 0 and (nx, ny) not in visited:
                queue.append((nx, ny))  # 将可达的点加入队列
                visited.add((nx, ny))  # 标记已访问过的点
    return False  # 没有找到终点，返回False

# 示例迷宫
maze = [
    [0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
    [0, 1, 1, 0, 1, 1, 1, 0, 1, 0],
    [0, 1, 1, 0, 1, 1, 1, 0, 1, 0],
    [0, 1, 1, 1, 1, 0, 0, 1, 1, 0],
    [0, 1, 0, 0, 0, 1, 1, 1, 1, 0],
    [0, 1, 1, 1, 0, 1, 1, 1, 1, 0],
    [0, 1, 0, 1, 1, 1, 0, 1, 1, 0],
    [0, 1, 0, 0, 0, 1, 0, 0, 1, 0],
    [0, 0, 1, 1, 1, 1, 1, 1, 1, 0],
    [0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
]

start = (1, 1)  # 起点
end = (8, 8)  # 终点

if bfs(maze, start, end):
    print("找到了一条从起点到终点的路径！")
else:
    print("没有从起点到终点的路径！")

在上面的代码中，我们使用了一个队列queue来存放待访问的节点。每次从队列中取出一个节点(x, y)，然后依次访问其上下左右四个方向的节点，如果该节点未被访问过且可达，则将其加入队列，并标记为已访问过。不断重复这个过程，直到找到终点或队列为空。如果找到了终点，则返回True，否则返回False。

需要注意的是，在上面的代码中，我们使用了一个集合visited来记录已访问过的节点，这是为了避免重复访问同一个节点。同时，我们还需要判断当前节点是否越界和是否为障碍物，以确保只访问可达节点。