迷宫问题 深度优先搜索

迷宫问题可以使用深度优先搜索算法来解决。深度优先搜索是一种用于遍历或搜索树或图的算法，它从根节点开始，沿着一个分支尽可能深入地搜索，直到搜索到叶子节点或者满足某个条件时回溯到上一层节点继续搜索。

在迷宫问题中，我们可以将迷宫表示为一个二维数组，其中0表示可以通过的路，1表示墙或者障碍物。我们从起点开始搜索，每次选择一个可行的方向，直到到达终点或者无法继续前进时回溯，尝试其他方向。

下面是一份迷宫问题深度优先搜索的 Python 代码示例：

def dfs(maze, visited, start, end):
    # 如果起点和终点相同，则返回 True
    if start == end:
        return True
    # 标记当前节点为已访问
    visited[start[0]][start[1]] = True
    # 定义四个方向的偏移量
    directions = [(0, 1), (0, -1), (1, 0), (-1, 0)]
    # 尝试四个方向
    for d in directions:
        # 计算下一个节点的坐标
        x = start[0] + d[0]
        y = start[1] + d[1]
        # 判断下一个节点是否越界或者已经访问过
        if x < 0 or x >= len(maze) or y < 0 or y >= len(maze[0]) or visited[x][y] or maze[x][y] == 1:
            continue
        # 递归搜索下一个节点
        if dfs(maze, visited, (x, y), end):
            return True
    # 回溯到上一层节点
    return False

# 调用函数进行搜索
maze = [[0, 1, 0, 0], [0, 0, 0, 1], [0, 1, 0, 0], [0, 1, 1, 0]]
visited = [[False for _ in range(len(maze[0]))] for _ in range(len(maze))]
start = (0, 0)
end = (3, 3)
print(dfs(maze, visited, start, end))

在上面的代码中，我们使用了一个二维数组 visited 来记录每个节点是否访问过，防止重复访问。我们也可以用一个 set 或者 dict 来实现 visited。