深度优先搜索的经典例题

深度优先搜索（DFS）是图遍历算法中的一种。在搜索过程中，从起点开始，沿着一条路径一直走到底，直到无法再走下去时，返回前一节点，继续试探下一条路径。

经典的深度优先搜索例题是“迷宫问题”。假设有一个 n×m 的迷宫，其中的障碍物用 1 表示，空格用 0 表示。现在要求从起点 (0,0) 出发，到达终点 (n-1,m-1)。可以向上、下、左、右四个方向移动，但不能穿过障碍物。

我们可以用 DFS 来解决这个问题。首先从起点开始，按照上、右、下、左的顺序依次试探四个方向。如果能够走到终点，就直接返回 True。如果不能走到终点，则在当前位置标记为已访问，然后按照上、右、下、左的顺序递归试探下一步。如果四个方向都试过了，还是无法到达终点，就返回 False。

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

def dfs(x, y, maze):
    if x == len(maze) - 1 and y == len(maze[0]) - 1:
        return True
    if x < 0 or x >= len(maze) or y < 0 or y >= len(maze[0]) or maze[x][y] == 1:
        return False
    maze[x][y] = 1
    if dfs(x-1, y, maze) or dfs(x, y+1, maze) or dfs(x+1, y, maze) or dfs(x, y-1, maze):
        return True
    maze[x][y] = 0
    return False

调用 dfs(0, 0, maze)，其中 maze 是一个二维数组，表示迷宫。如果返回 True，表示可以从起点走到终点；如果返回 False，表示无法到达终点。