python dfs递归实现迷宫问题

好的，下面是 Python 中 DFS 递归实现迷宫问题的代码示例：

# 定义迷宫地图，0 表示可走，1 表示障碍物
maze = [
    [0, 1, 0, 0, 0],
    [0, 1, 0, 1, 0],
    [0, 0, 0, 0, 0],
    [0, 1, 1, 1, 0],
    [0, 0, 0, 1, 0],
]

# 定义迷宫大小
n = len(maze)
m = len(maze[0])

# 定义标记数组，标记每个位置是否已经访问过
visited = [[False] * m for _ in range(n)]

# 定义终点位置
end = (4, 3)

# 定义方向数组，表示上下左右四个方向
directions = [(-1, 0), (1, 0), (0, -1), (0, 1)]


def dfs(x, y):
    # 如果当前位置就是终点位置，则直接返回 True
    if (x, y) == end:
        return True
    
    # 标记当前位置已经访问过
    visited[x][y] = True
    
    # 枚举四个方向
    for dx, dy in directions:
        nx, ny = x + dx, y + dy
        
        # 判断是否越界，是否已经访问过，是否是障碍物
        if 0 <= nx < n and 0 <= ny < m and not visited[nx][ny] and maze[nx][ny] == 0:
            # 递归搜索下一个位置
            if dfs(nx, ny):
                return True
    
    # 如果四个方向都没找到终点，则返回 False
    return False


# 在起点位置开始搜索
start = (0, 0)
if dfs(start[0], start[1]):
    print("可以到达终点！")
else:
    print("无法到达终点！")

这段代码中，我们先定义了一个迷宫地图 `maze`，然后定义了迷宫的大小 `n` 和 `m`，以及标记数组 `visited` 和终点位置 `end`。

接着，我们定义了一个 DFS 函数 `dfs`，它的参数是当前位置的坐标 `(x, y)`，表示从这个位置开始搜索。

在 `dfs` 函数中，我们首先判断当前位置是否是终点位置，如果是，则直接返回 True。

然后，我们标记当前位置已经访问过，并枚举当前位置可以走的四个方向。对于每个方向，我们判断是否可以走，如果可以，则递归搜索下一个位置。如果在四个方向中找到了终点位置，则返回 True。

最后，在主函数中，我们从起点位置开始搜索，如果可以到达终点，则输出“可以到达终点！”；否则输出“无法到达终点！”。