python迷宫问题算法

Python 中有许多算法可以用来解决迷宫问题，以下是其中一种基于深度优先搜索（DFS）的算法：

1. 定义一个包含所有可能移动方向（上下左右）的列表。
2. 创建一个空的栈，并将起始位置压入栈中。
3. 创建一个空的集合，用于存储已经访问过的位置。
4. 循环执行以下步骤，直到栈为空：
* 弹出栈顶元素并将其标记为已访问。
* 如果该元素是终点位置，则返回路径。
* 否则，对于每个可能的移动方向，如果该方向上的位置未被访问且不是墙，则将该位置添加到栈中。
5. 如果栈为空，说明没有找到路径，返回空。

下面是一个简单的 Python 实现：

def find_path(maze, start, end):
    directions = [(0, -1), (0, 1), (-1, 0), (1, 0)] # 上下左右四个方向
    stack = [start] # 起点入栈
    visited = set() # 已访问的位置
    while stack:
        curr = stack.pop() # 弹出栈顶元素
        visited.add(curr) # 标记为已访问
        if curr == end: # 如果找到终点
            return build_path(curr, start)
        for d in directions: # 对于每个方向
            next_pos = (curr[0] + d[0], curr[1] + d[1])
            if next_pos not in visited and is_valid(next_pos, maze): # 如果未访问且不是墙
                stack.append(next_pos) # 加入栈中
    return None # 没有找到路径

def is_valid(pos, maze):
    x, y = pos
    if x < 0 or x >= len(maze) or y < 0 or y >= len(maze[x]):
        return False # 超出边界
    return maze[x][y] != 1 # 不是墙

def build_path(curr, start):
    path = []
    while curr != start:
        path.append(curr)
        curr = curr[2] # 从终点往回走
    path.append(start)
    return path[::-1] # 反转路径，使其从起点到终点

其中，`maze` 是一个二维数组，表示迷宫，其中 0 表示可以通过的路径，1 表示墙；`start` 和 `end` 是起点和终点的坐标，例如 `(0, 0)` 表示左上角。`build_path` 函数用于构建路径，其中 `curr[2]` 表示从当前位置往回走的前一个位置。