DFS（深度优先搜索）

    给定一个n*m 的二维整数数组，用来表示一个迷宫，数组中只包含.或#，其中.表示可以走的路，#表示不可通过的墙壁。   最初，有一个人位于左上角(0, 0)处，已知该人每次可以向上、下、左、右任意一个方向移动一个位置。  请问，该人从左上角移动至右下角处，至少需要移动多少次。  数据保证(0, 0)处和(n-1, m-1)处的数字为 0，且一定至少存在一条通路。

输入格式第一行包含两个整数 n 和 m。接下来 n 行，每行包含 m（.或#），表示完整的二维数组迷宫。输出格式输出一个整数，表示从左上角移动至右下角的最少移动次数。数据范围1≤n,m≤100输入样例：5 5.#....#..#.......###....#.输出样例：8

递归深入探索路径 + 回溯恢复状态”，穷举从起点到终点的所有可能路径，最终筛选出最短的那条：



拆解成 4 个关键步骤（以迷宫为例）：终止条件：到达终点 / 越界 / 不合法，停止当前路径的探索；遍历方向：尝试所有可选的移动方向（如下右上左）；标记 + 递归：标记当前位置为 “已访问”，递归探索下一个位置；回溯：递归返回后，恢复当前位置为 “未访问”，让其他路径复用该位置。

模块 1：导入模块 + 设置递归深度import sys：作用：导入 Python 的系统模块sys，这个模块提供了和 Python 解释器交互的底层功能。设计动机：我们需要用到sys模块里的setrecursionlimit函数来调整递归深度，所以必须先导入。sys.setrecursionlimit(100000)：作用：将 Python 默认的递归最大深度（约 1000 层）修改为 100000 层。设计动机：DFS 是递归实现的，迷宫路径可能很长（比如 100x100 迷宫的路径步数可能超过 1000），默认递归深度会导致 “栈溢出错误（RecursionError）”；设为 100000 是为了给递归足够的 “栈空间”，确保能遍历完所有可能的路径（数值足够大且不浪费内存）。

模块 2：全局变量初始化n, m = 0,0：作用：定义两个变量存储迷宫的行数（n）和列数（m），初始值为 0，后续会被输入覆盖。设计动机：迷宫的行列数是后续所有操作的基础（比如判断边界、遍历地图），需要全局共享（递归函数中要用到）。a = [[0 for _ in range(100)] for _ in range(100)]：作用：创建一个 100 行 ×100 列的二维列表，用于存储迷宫的每个位置（.可走 /#墙）。设计动机：迷宫是二维结构（行 + 列），二维列表能精准对应迷宫的每个位置（a[i][j]表示第 i 行第 j 列）；初始值设为 0 是 “占位符”，后续会被输入的./#覆盖；100x100 的大小适配题目 “1≤n,m≤100” 的范围，避免下标越界；用for _ in range(100)嵌套而不是[[0]*100]*100，是为了让每一行都是独立的列表（防止改一行影响所有行）。vis = [[False for _ in range(100)] for _ in range(100)]：作用：创建和迷宫同大小的二维布尔列表，标记每个位置是否被走过（True= 已走，False= 未走）。设计动机：DFS 是 “穷举路径”，如果不标记已走的位置，会出现 “回头走、绕圈” 的情况（比如从 (0,0) 到 (0,1)，又走回 (0,0)），导致无限递归；布尔值False/True轻量，且能清晰区分 “未访问 / 已访问”。ans = 10000000：作用：存储最短路径的长度，初始值设为一个极大的数（远大于迷宫最大可能步数：100+100=200）。设计动机：初始值要足够大，确保第一次找到有效路径时，min(ans, step)能正确更新为第一个路径的步数；后续遍历到更短的路径时，会通过min函数不断更新为更小的值，最终保留最小值。dir = [(1, 0), (0, 1), (-1, 0), (0, -1)]：作用：定义四个移动方向的坐标偏移量，分别对应 “下、右、上、左”（第一个数是行偏移，第二个是列偏移）。设计动机：移动方向是固定的四个，用列表封装后，只需一个循环就能遍历所有方向，避免重复写 4 次 “下 / 右 / 上 / 左” 的判断代码；偏移量的设计符合二维坐标规则：行 + 1 = 向下走，列 + 1 = 向右走，行 - 1 = 向上走，列 - 1 = 向左走。

模块 3：DFS 核心递归函数

函数参数说明

dfs(x, y, step)的三个参数：x, y：当前所在的迷宫位置（行、列）；step：从起点走到当前位置的步数。设计动机：递归的核心是 “当前状态”，这三个参数完整描述了 “走到哪 + 走了多少步”，是探索下一个位置的基础。

逐行解释global ans：作用：声明函数内要修改的ans是全局变量，而非局部变量。设计动机：Python 中，函数内默认只能读取全局变量，修改会被视为创建局部变量；ans是存储最短路径的核心变量，需要在递归的所有层级中共享和修改，所以必须声明global。if x == n - 1 and y == m - 1:：作用：判断当前位置是否是迷宫的右下角终点（行号 = n-1，列号 = m-1，因为下标从 0 开始）。设计动机：终点是递归的 “终止条件” 之一，一旦到达，就无需继续探索方向；把终点判断放在遍历方向之前，是为了 “提前终止”—— 如果当前已经到终点，就不用再遍历四个方向，减少无效递归。ans = min(ans, step)：作用：比较当前最短路径ans和当前路径步数step，保留更小的值（即更新最短路径）。设计动机：DFS 会遍历所有路径，每到一次终点就记录一次步数，min能确保最终ans是所有路径中最短的；用step+1是错误的：因为step已经是走到当前终点的步数（起点 step=0，走一步到下一个位置 step+1），终点无需额外 + 1。return：作用：终止当前递归层级，回到上一层递归（比如从终点返回到上一个位置）。设计动机：到达终点后，没有必要再遍历四个方向，return能减少不必要的计算，提升效率。for i in range(4):：作用：遍历四个移动方向（dir列表的 4 个元素）。设计动机：四个方向是固定的，循环遍历能避免重复写 4 段几乎一样的代码（简洁、易维护）。xx = x + dir[i][0]; yy = y + dir[i][1]：作用：根据当前位置(x,y)和方向偏移量，计算新位置(xx, yy)的坐标。设计动机：偏移量的设计让坐标计算更简洁（比如向下走就是行 + 1，列不变），无需手动写x+1/y+1等。x = 当前位置的行号（向下变大），y = 当前位置的列号（向右变大）；dir 是方向数组，每个元素是 (行偏移量, 列偏移量)，比如 (1,0) 表示 “行 + 1，列不变”（向下走）；i 是方向的索引（0 = 下、1 = 右、2 = 上、3 = 左）。if 0 <= xx < n and 0 <= yy < m and not vis[xx][yy] and a[xx][yy] == '.'：作用：检查新位置(xx, yy)是否 “合法”（能走），四个条件缺一不可：0 <= xx < n and 0 <= yy < m：新位置在迷宫边界内（不越界）；not vis[xx][yy]：新位置未被走过（避免绕圈 / 回头）；a[xx][yy] == '.'：新位置是可走的路（不是墙#）。设计动机：越界会导致下标错误，走回头路会无限递归，走墙是无效路径 —— 这三个过滤条件能确保只探索 “有效路径”；条件按 “边界→访问→可通行” 的顺序判断，是因为边界判断最快（数值比较），能提前过滤无效位置，提升效率。vis[xx][yy] = True：作用：标记新位置为 “已访问”。设计动机：防止后续递归中再次走到这个位置（比如从(xx,yy)又走回(x,y)），避免无限循环。dfs(xx, yy, step + 1)：作用：递归调用 DFS，探索新位置(xx, yy)，步数 + 1（走到新位置需要多走一步）。设计动机：DFS 的核心是 “深入探索”—— 从当前位置走到新位置，继续探索下一个位置，直到终点或无路可走。vis[xx][yy] = False：作用：回溯 —— 将新位置的访问标记恢复为 “未访问”。设计动机：这是 DFS 最核心的一步！当从(xx, yy)的递归返回后（即探索完(xx, yy)的所有路径），需要把这个位置 “释放”，让其他路径能走到这里；比如：从(0,0)走到(0,1)，探索完(0,1)的所有路径后，恢复(0,1)为未访问，这样后续从(1,0)出发的路径也能走到(0,1)。

模块 4：主程序（入口逻辑）

逐行解释if __name__ == "__main__":：作用：判断当前脚本是否是 “主程序运行”（而非被导入为模块），如果是则执行后续代码。设计动机：这是 Python 的规范写法，能避免脚本被导入时自动执行核心逻辑（比如其他文件导入这个脚本时，不会触发迷宫输入和 DFS）。n, m = map(int, input().split())：作用：读取用户输入的第一个行（两个整数），分别赋值给n（行数）和m（列数）。设计动机：获取迷宫的基本尺寸，为后续读取地图、判断边界提供依据。for i in range(n): row = input().strip(); for j in range(m): a[i][j] = row[j]：作用：逐行读取迷宫地图，将每个字符（./#）存入二维列表a的对应位置。设计动机：input().strip()：去除输入行的换行符 / 空格，确保读取的字符纯是迷宫的./#；外层循环遍历行（i），内层循环遍历列（j），正好对应a[i][j]的二维结构，将输入的字符串 “映射” 为迷宫数组。vis[0][0] = True：作用：将起点(0,0)标记为 “已访问”。设计动机：起点是路径的开始，防止递归中回头走起点（比如从(0,1)又走回(0,0)）。dfs(0, 0, 0)：作用：启动 DFS 递归，从起点(0,0)开始探索，初始步数为 0（还没移动）。设计动机：这是整个算法的 “入口”，触发所有路径的遍历。print(ans)：作用：输出最短路径的长度。设计动机：题目要求输出最少移动次数，ans经过所有路径的遍历后，已经存储了最小值，直接输出即可。

✅ 适用：找迷宫的所有可能路径；判断图 / 迷宫是否连通；子集、排列、组合等穷举问题；找是否存在满足条件的路径。