当前位置：首页 > article >正文

（算法竞赛）DFS深搜4——迷宫第一条路问题解析与代码实现

article 2025/1/26 14:21:48

题目描述
已知一个 N × N 的迷宫，允许往上、下、左、右四个方向行走，现请你 按照左、上、右、下顺序 进行搜索，找出第一条从左上角到右下角的路径。

输入
输入数据有若干行，第一行有一个自然数 N（N≤20），表示迷宫的大小；
其后有 N 行数据，每行有 N 个 0 或 1（数字之间没有空格，0 表示可以通过，1 表示不能通过），用以描述迷宫地图。入口在左上角 (1,1) 处，出口在右下角 (N,N) 处。
所有迷宫保证存在从入口到出口的可行路径。

输出
输出数据仅一行，为按照要求的搜索顺序找到的从入口到出口的第一条路径（搜索顺序：左、上、右、下）。

样例

输入

输出

(1,1)->(1,2)->(1,3)->(2,3)->(2,4)->(3,4)->(4,4)

来源
深搜递归

题解

输入迷宫数据
n = int(input())
a = [input() for _ in range(n)]
这部分代码首先读取迷宫的大小 n，然后逐行读取迷宫的布局，存储为一个二维字符串数组 a。迷宫的每个格子用 0 或 1 表示。
初始化访问标记数组
vis = [[0] * n for _ in range(n)]
为了避免重复访问同一个格子，代码中使用了一个二维数组 vis 来标记每个格子是否已被访问。初始时，所有格子标记为未访问。
方向数组
dx = [0, -1, 0, 1]
dy = [-1, 0, 1, 0]
这两个数组定义了搜索的方向，分别对应左、上、右、下。通过索引 i，可以同时从 dx 和 dy 中获取对应的偏移量。
深度优先搜索（DFS）函数
def dfs(xx, yy, path):
    if xx == n - 1 and yy == n - 1:
        print("->".join(path + [(f"({xx + 1},{yy + 1})")]))
        return True
    vis[xx][yy] = 1
    for i in range(4):
        x, y = xx + dx[i], yy + dy[i]
        if 0 <= x < n and 0 <= y < n and vis[x][y] != 1 and a[x][y] == '0':
            if dfs(x, y, path + [(f"({xx + 1},{yy + 1})")]):
                return True
    return False
递归终止条件：当当前格子 (xx, yy) 到达右下角 (n-1, n-1) 时，表示找到了一条从入口到出口的路径。此时，将路径打印出来并返回 True。

标记当前格子为已访问：通过 vis[xx][yy] = 1，将当前格子标记为已访问，避免重复搜索。

搜索相邻格子：按照左、上、右、下的顺序依次尝试移动到相邻格子。如果相邻格子在迷宫范围内、未被访问且可以通过（即值为 0），则递归调用 dfs 函数。

路径记录：每次递归调用时，将当前格子的坐标加入路径 path 中。路径以字符串形式存储，格式为 (x,y)。

回溯：如果当前路径不可行（即递归调用返回 False），则回溯到上一层继续搜索。
从入口开始搜索

Python复制
dfs(0, 0, [])
从迷宫的左上角 (0, 0) 开始调用 dfs 函数，初始路径为空。
代码运行逻辑

递归调用：dfs 函数通过递归调用自身，不断深入搜索迷宫的路径。每次递归调用都会尝试移动到相邻的格子，并将路径记录下来。

回溯机制：如果在某个方向上无法继续前进（例如遇到障碍物或已访问的格子），则回溯到上一个格子，尝试其他方向。

路径输出：当找到一条从入口到出口的路径时，路径会以 (x1,y1)->(x2,y2)->...->(xn,yn) 的格式输出。

代码优势与局限性

优势：DFS 使用递归实现，代码简洁，逻辑清晰，适合解决迷宫等路径搜索问题。

局限性：由于递归调用的深度可能较大，可能会导致栈溢出问题。此外，DFS 不一定能找到最短路径，仅能找到一条可行路径。

总结

这段代码通过深度优先搜索（DFS）递归实现了从迷宫入口到出口的路径搜索。它利用了递归的回溯机制，避免了重复访问格子，并通过方向数组实现了按顺序搜索。

完整代码
def dfs(xx, yy, path):
    # 如果到达右下角，输出路径并返回
    if xx == n - 1 and yy == n - 1:
        print("->".join(path + [(f"({xx + 1},{yy + 1})")]))
        return True
    # 标记当前格子为已访问
    vis[xx][yy] = 1
    for i in range(4):
        x, y = xx + dx[i], yy + dy[i]
        if 0 <= x < n and 0 <= y < n and vis[x][y] != 1 and a[x][y] == '0':
            # 将当前格子加入路径
            if dfs(x, y, path + [(f"({xx + 1},{yy + 1})")]):
                return True
    # 如果当前路径不可行，回溯
    return False
# 输入迷宫大小
n = int(input())
# 输入迷宫矩阵
a = [input() for _ in range(n)]
# 初始化访问标记数组
vis = [[0] * n for _ in range(n)]
dx = [0, -1, 0, 1]
dy = [-1, 0, 1, 0]
# 从左上角开始搜索
dfs(0, 0, [])