深度优先搜索经典例题

一个经典的深度优先搜索（DFS）例题是迷宫问题。

假设有一个迷宫，其中包含了一些墙壁和通道。你的任务是找到从起点到终点的路径。在迷宫中，你只能沿上、下、左、右四个方向移动，不能斜向移动，并且不能穿过墙壁。

DFS 是一种递归的搜索算法，在解决迷宫问题时非常有效。它的基本思想是从起点开始，依次尝试每个可能的移动方向，直到找到路径或者无法继续移动为止。如果遇到无法继续移动的情况，就会回溯到上一个位置，尝试其他方向。

下面是一个简单的示例代码，演示了如何使用深度优先搜索解决迷宫问题：

def dfs(maze, start, end):
    rows = len(maze)
    cols = len(maze[0])

    # 创建一个与迷宫大小相同的二维数组来记录访问状态
    visited = [[False] * cols for _ in range(rows)]

    # 定义上、下、左、右四个方向的移动向量
    directions = [(0, 1), (0, -1), (1, 0), (-1, 0)]

    def can_move(row, col):
        # 判断当前位置是否可以移动
        if row < 0 or row >= rows or col < 0 or col >= cols:
            return False
        if maze[row][col] == 1 or visited[row][col]:
            return False
        return True

    def dfs_helper(row, col):
        # 标记当前位置为已访问
        visited[row][col] = True

        # 如果当前位置是终点，返回True表示找到了路径
        if (row, col) == end:
            return True

        # 尝试四个移动方向
        for direction in directions:
            new_row = row + direction[0]
            new_col = col + direction[1]
            if can_move(new_row, new_col):
                if dfs_helper(new_row, new_col):
                    return True

        # 如果四个方向都无法找到路径，回溯到上一个位置
        return False

    # 从起点开始进行深度优先搜索
    return dfs_helper(start[0], start[1])

这只是一个简单的演示，实际应用中可能需要更复杂的逻辑来处理不同的情况。希望能帮到你！