用队列求解迷宫所有路径Python

在Python中，使用队列数据结构解决迷宫的所有路径问题通常涉及到深度优先搜索（DFS）或广度优先搜索（BFS）。这里我们以广度优先搜索为例，因为它可以保证找到最短路径。以下是使用`deque`（双端队列）实现的简单示例：

from collections import deque

def bfs_maze(maze, start, end):
    if not maze or start == end or not maze[start]:
        return []

    directions = [(0, 1), (0, -1), (1, 0), (-1, 0)]  # 上下左右四个方向
    queue = deque([(start, [start])])
    visited = set()

    while queue:
        row, path = queue.popleft()
        
        if row == end and maze[row][end]:  # 到达终点且路是通的
            return path
        
        for dx, dy in directions:
            new_row, new_col = row + dx, col + dy
            
            # 检查新位置是否合法、未访问过并且路是通的
            if 0 <= new_row < len(maze) and 0 <= new_col < len(maze[0]) \
                    and maze[new_row][new_col] and (new_row, new_col) not in visited:
                visited.add((new_row, new_col))
                queue.append((new_row, path + [new_col]))

# 示例迷宫矩阵，其中1表示墙，0表示空地，S和E分别表示起点和终点
maze = [[1, 0, 0, 0], [1, 1, 0, 1], [0, 0, 0, 0], [1, 1, 0, 0]]
start = (0, 0)
end = (len(maze) - 1, len(maze[0]) - 1)

paths = bfs_maze(maze, start, end)
if paths:
    print("找到了从{}到{}的所有路径：".format(start, end))
    for path in paths:
        print(path)
else:
    print("找不到从{}到{}的路径。".format(start, end))