用pytharm实现广度搜索求解迷宫

在Python中实现广度优先搜索（BFS）用于解决迷宫问题，通常我们会采用队列数据结构。以下是一个简单的步骤：

1. 定义迷宫矩阵（二维列表），其中0表示通行路径，1表示障碍物。

2. 初始化：设置起点（start）到终点（end）之间的距离为无穷大（例如`INF`），并将起点的距离设为0。同时创建一个空队列，将起点加入队列。

3. 迭代过程：
- 弹出队列的第一个元素（当前节点）。
- 检查该节点是否为目标节点，如果是，则返回从起点到目标的最短路径。
- 如果不是，遍历其相邻的节点（上下左右四个方向）：
- 如果新节点是空白格且未访问过，更新它的距离值为当前节点的距离加一，并将其加入队列。

4. 遍历完整个过程，如果没有找到目标，说明迷宫无解，可以返回一个特殊标记，如None或False。

5. 返回从起点到终点的最短路径，如果存在，通常是一个包含节点位置的列表或者二维坐标。

from collections import deque

def bfs_maze(maze, start, end):
    queue = deque([(start, [start])])
    distances = {start: 0}
    
    while queue:
        current, path = queue.popleft()
        
        if current == end:
            return path
        
        for neighbor in [(current[0] + dx, current[1] + dy) for dx, dy in [(0, -1), (0, 1), (-1, 0), (1, 0)]]:
            x, y = neighbor
            if 0 <= x < len(maze) and 0 <= y < len(maze[0]) and maze[x][y] == 0 and neighbor not in distances:
                distances[neighbor] = distances[current] + 1
                queue.append((neighbor, path + [neighbor]))
                
    return None  # 迷宫无解

# 示例用法
maze = [
    [0, 0, 0, 0],
    [0, 1, 0, 1],
    [0, 0, 0, 0]
]

start = (0, 0)
end = (2, 2)

solution = bfs_maze(maze, start, end)
if solution is not None:
    print("Shortest path:", solution)
else:
    print("No solution found.")