用栈解决迷宫问题

解决迷宫问题的常见方法是使用深度优先搜索（DFS）或广度优先搜索（BFS）。其中，DFS 可以使用栈来实现。

具体实现过程如下：

1. 定义一个栈，用于存储当前路径。

2. 定义一个访问标记数组，用于标记已经访问过的位置。

3. 将起点入栈，并将起点标记为已访问。

4. 当栈不为空时，取出栈顶元素，判断是否为终点。如果是，则输出路径并结束程序；否则，将当前位置的所有未访问的相邻位置依次入栈，并标记为已访问。

5. 重复步骤 4 直到找到终点或栈为空。

以下是一个简单的 Python 代码示例：

maze = [
    [0, 1, 0, 0],
    [0, 1, 0, 1],
    [0, 0, 0, 0],
    [0, 1, 1, 0],
]

start = (0, 0)
end = (3, 3)

stack = [start]
visited = set([start])

while stack:
    x, y = stack.pop()
    if (x, y) == end:
        print("路径：", visited)
        break
    for dx, dy in [(1, 0), (0, 1), (-1, 0), (0, -1)]:  # 四个方向
        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:
            stack.append((nx, ny))
            visited.add((nx, ny))

其中，`maze` 表示迷宫地图，0 表示可以通过的空地，1 表示墙；`start` 和 `end` 分别表示起点和终点，这里使用了元组来表示坐标。`visited` 是一个集合，用于记录已经访问过的位置。在每次取出栈顶元素后，依次检查四个方向的相邻位置，如果是空地且未访问过，则入栈并标记为已访问。如果找到了终点，则输出路径并结束程序。