3.用栈求解迷宫问题 问题描述：给定一个M×N的迷宫图、入口与出口、行走规则。求一条从指定入口到出口的路径。所求路径必须是简单路径，即路径不重复。请编写出代码。

在使用栈来求解迷宫问题时，我们可以采用广度优先搜索（BFS）算法，因为BFS通常用于寻找最短路径。这里是一个使用Python实现的基本流程：

1. 首先，创建一个二维列表`maze`表示迷宫，其中`maze[i][j]`为True表示该位置可走，False表示不可走；然后定义起始点`start`和结束点`end`。

2. 初始化一个队列`queue`，将起始点加入队列，并标记起始点为已访问`visited[start] = True`。

3. 开始循环，当队列非空时：
- 弹出队首元素`(x, y)`。
- 如果当前点是终点，则找到了一条路径，记录并返回。
- 遍历当前点的所有邻居`(dx, dy)`，判断其是否在迷宫范围内且可走，如果满足条件，将其加入队列并标记为已访问。

4. 使用一个集合`seen`来存储已经访问过的节点，避免重复路径。

5. 如果没有找到路径，说明从起始点到终点没有可达的简单路径。

以下是完整的Python代码实现：

from collections import deque

def bfs_maze(maze, start, end):
    rows, cols = len(maze), len(maze[0])
    queue = deque([(start[0], start[1], [])])  # 存储(x, y, path)
    visited = set()  # 已访问节点
    seen = set()

    while queue:
        x, y, path = queue.popleft()
        if (x, y) == end:
            return path + [(x, y)]  # 返回路径

        if (x, y) not in seen:
            seen.add((x, y))

            # 检查上下左右四个方向
            for dx, dy in [(0, -1), (0, 1), (-1, 0), (1, 0)]:
                nx, ny = x + dx, y + dy
                if 0 <= nx < rows and 0 <= ny < cols and maze[nx][ny] and (nx, ny) not in visited:
                    queue.append((nx, ny, path + [(x, y)]))  # 添加新节点到队列
                    visited.add((nx, ny))  # 更新已访问节点

    return None  # 未找到路径

# 示例
maze = [
    [1, 0, 0, 1],
    [0, 1, 0, 0],
    [0, 0, 1, 1],
    [1, 1, 0, 0]
]
start = (0, 0)
end = (3, 3)
path = bfs_maze(maze, start, end)
if path:
    print("找到了路径", path)
else:
    print("未找到路径")