最近刷题时碰上一个特别有意思的搜索题题目就叫“路径之谜”。给定一张 n x n 的棋盘骑士从左上角出发每一步只能上下左右移动最终要走到右下角。奇怪的是题目不问你“有多少条路径”也不问你“最短路径是什么”而是提前告诉你最终走过的路径中每一行总共经过了多少个格子、每一列总共经过了多少个格子要你反推出具体是沿着哪条路径走的。第一眼看到这题我脑子里蹦出来的解法就是 DFS也就是深度优先搜索。原因很简单这是一个典型的“路径搜索 回溯”问题DFS 天然适合在搜索树上一条路走到底走不通再回头同时还可以利用行列计数做剪枝效率并不差。这篇文章我打算把“路径之谜”完整拆开从问题建模、状态设计、剪枝技巧到实际手写代码、调试排坑全部过一遍。不管你是刚开始接触 DFS 的算法新手还是准备面试、打比赛的选手这篇文章都能给你一些能直接落地的经验。1. 问题建模与思路拆解1.1 谜面到底在说什么先把题目翻译成人话。假设棋盘大小是 n x n格子从 (0,0) 到 (n-1,n-1)。骑士从 (0,0) 出发每走到一个格子这个格子就算被“访问”过一次。最终到达 (n-1,n-1) 时我们手里有两个数组rowCnt[i]第 i 行被访问过的格子总数colCnt[j]第 j 列被访问过的格子总数。当然棋盘的起点和终点都算被访问过。路径必须是一条简单路径也就是同一个格子不能走两次否则访问次数就没法控制搜索空间也会爆炸。举个例子n3 时如果 rowCnt [1, 2, 1]colCnt [2, 1, 1]你能想象出路径吗手工推一下起点 (0,0) 使得第0行和第0列都有1个格子被访问。终点 (2,2) 使得第2行第2列也各占1个。中间剩余的行列计数就只能靠路径经过的中间格子去填补。这种题目的核心难点在于路径是隐式的你要在所有可能的 DFS 探索路径中找到满足行列计数约束的那一条。1.2 为什么首选 DFS 而不是 BFS面对路径搜索问题很多人第一反应是 BFS因为 BFS 适合求最短路径。但“路径之谜”并不是求最短而是求“满足精确计数约束的一条路径”。如果你用 BFS 去遍历状态每个状态除了坐标还得带着完整的访问标记和行列计数内存开销会非常大。而且 BFS 是按层扩展的想记录一条完整路径需要额外维护前驱节点处理起来特别啰嗦。DFS 就不一样。DFS 天然是“一条路走到黑”它在递归栈里自带当前路径的全部上下文访问标记、行列计数、路径列表。走到终点时如果计数恰好满足要求直接输出路径即可。走不通就回溯把状态恢复成进入之前的样子。这种“状态即上下文”的特性让 DFS 在路径枚举类问题里几乎是标准答案。另外DFS 配上剪枝以后实际搜索空间远小于理论最坏情况。BFS 很难在“计数约束”上做高效剪枝因为它是逐层扩散的你没法提前判断某条分支已经不可能满足剩余行列计数。而 DFS 可以在每一步递归前检查所有剪枝条件发现不合法就立刻掉头效率可以做到非常可观。1.3 路径之谜与哈密顿路径的关系如果只靠“每个格子不能重复走”这一条规则问题本质上是在棋盘上找一条哈密顿路径的变体。哈密顿路径要求经过所有顶点一次而路径之谜只要求行、列计数恰好匹配并没有说必须经过多少个格子所以比标准哈密顿路径更宽松但也因为计数约束的存在反而多了一些强剪枝条件。理解这一点很重要。遇到这种题目不要直接陷入“枚举所有路径”的蛮力思维而是要把问题拆成三件事搜索空间所有从起点到终点的简单路径约束条件行计数、列计数必须精确匹配优化手段通过当前已用计数、剩余计数、剩余可访问格子数来剪枝。这样一来DFS 的代码结构就变得非常清晰了。2. 核心细节设计状态、方向与剪枝2.1 状态设计与参数传递写 DFS 之前先想清楚递归函数的参数需要带哪些东西。这里我习惯用“当前坐标 当前已访问行计数 当前已访问列计数 当前路径”来刻画一个 DFS 状态。dfs(x, y, curRow, curCol, path)其中curRow[i]表示当前路径中第 i 行已经被访问的格子数curCol[j]表示第 j 列已经被访问的格子数。path是已经走过的格子序列用来在最终输出时还原整条路径。有人会问visited二维数组要不要作为参数传我的建议是用全局变量或外部数组统一管理递归前后做标记和恢复。因为visited在整个搜索过程中是全局共享的每一层递归进入时标记当前格子回溯时取消标记。如果作为参数传每次递归都要拷贝一份二维数组n 稍微大一点性能就会很难看。同样的curRow和curCol也可以用全局数组维护进入递归前curRow[x]、curCol[y]回溯时再减回去。这样既省内存又保证了状态的一致性。2.2 方向枚举与回溯还原经典四方向遍历是这类题的基础操作。我一般这样定义方向数组DIRS [(-1, 0), (1, 0), (0, -1), (0, 1)]每次从当前格子出发尝试向四个方向移动。新坐标必须在棋盘范围内且不能是已访问的格子。然后递归进入下一步。回溯的时候除了要把visited[nx][ny]恢复成False还要把curRow[nx]--、curCol[ny]--并且把path中最后加入的格子弹出。这里有一个特别容易踩的坑回溯顺序必须严格对称。你进入递归之前做了什么修改退出递归之后就必须全部撤销缺一个都会导致状态污染最终答案要么找不到要么找到一堆假路径。我在调试这种问题的时候会习惯在递归函数的开头打印当前状态肉眼检查回溯是否正确。2.3 三大剪枝策略缺一不可剪枝是“路径之谜”这类题目的灵魂。不加剪枝的裸 DFSn 稍微大到 8 或 9可能就卡死到怀疑人生。我实际使用中最有效的剪枝有三个。第一个是基础计数剪枝在递归过程中任何一行或一列的当前计数都不能超过目标值。一旦出现curRow[i] rowCnt[i]立即终止当前分支。这个剪枝最简单也最必要能挡掉大量无效探索。第二个是剩余可达性剪枝如果当前行计数已经等于目标值那么这一行剩下的格子就都不能再走了。反过来说如果当前行还差rowCnt[i] - curRow[i]个格子没走但这一行剩余的未访问格子数已经小于这个差值那也不可能满足条件直接剪掉。同理对列也做一遍。这种预判式剪枝特别考验对约束传播的理解但效果立竿见影。第三个是终点目标剪枝如果当前已经到达终点(n-1,n-1)别急着返回先检查所有行和列的计数是否完全等于目标值。如果等于记录答案并返回如果不等于继续回溯。另外如果路径已经走到终点但计数不匹配就不需要再继续扩展了因为终点之后没有合法移动除非允许走出棋盘显然不允许。另外还有一个常见优化是提前判断起点和终点的行列计数是否合法。因为起点和终点至少会计数一次如果rowCnt[0] 0或colCnt[0] 0或者rowCnt[n-1] 0或colCnt[n-1] 0那么根本不存在合法路径可以直接返回空。这种边界检查放在主函数里能省掉一次毫无意义的深度搜索。2.4 为什么访问标记不能省有人可能会说路径之谜的行列计数已经限制了每个格子最多走一次吗不一定。如果一个格子被走了两次那么它所在的行和列都会被多计数一次但单纯靠行列计数无法唯一排除所有重复访问的情况。比如一条路径绕了一圈回到同一个格子计数仍然可能恰好匹配但“路径”的定义通常不允许这样更关键的是允许重复访问会让搜索空间变成无穷大DFS 根本结束不了。所以visited标记必须放在 DFS 的核心逻辑里而且是全局共享的。每当进入一个格子就把它标记为已访问回溯时再取消标记。这样做不仅能保证路径是简单路径还能大幅压缩搜索空间因为每个格子在一条路径中最多出现一次。3. 实操过程完整手写“路径之谜”解法3.1 输入输出定义为了把代码写得清晰我们先约定输入格式第一行一个整数 n表示棋盘大小第二行 n 个整数表示 rowCnt[0] 到 rowCnt[n-1]第三行 n 个整数表示 colCnt[0] 到 colCnt[n-1]。输出要求如果存在合法路径按行走顺序输出路径上格子编号。这里有两种常见编号方式一种是按“行* n 列”的编号比如 (0,0) 编号为 0(0,1) 编号为 1另一种是按题目特定规则。我采用最常见的方式用x * n y表示格子编号路径序列直接输出编号数组。为了检验结果是否正确还需要写一个校验函数根据输出的路径重新计算行列计数与目标值对比。3.2 Python 实现DFS 剪枝直接看代码。import sys sys.setrecursionlimit(1000000) def solve_path_mystery(n, rowCnt, colCnt): # 边界检查起点和终点所在行列必须有容量 if rowCnt[0] 0 or colCnt[0] 0: return None if rowCnt[n-1] 0 or colCnt[n-1] 0: return None visited [[False] * n for _ in range(n)] curRow [0] * n curCol [0] * n path [] result [] # 计算某一行/列还剩多少个未访问格子用于第二类剪枝 def remaining_available(row_or_col, is_row): cnt 0 if is_row: for y in range(n): if not visited[row_or_col][y]: cnt 1 else: for x in range(n): if not visited[x][row_or_col]: cnt 1 return cnt def feasible(x, y): # 剪枝1行列计数不能超 if curRow[x] 1 rowCnt[x]: return False if curCol[y] 1 colCnt[y]: return False return True def dfs(x, y): # 进入格子更新状态 visited[x][y] True curRow[x] 1 curCol[y] 1 path.append(x * n y) # 如果到达终点 if x n - 1 and y n - 1: if curRow rowCnt and curCol colCnt: result.append(path[:]) return True # 终点计数不匹配直接回溯 visited[x][y] False curRow[x] - 1 curCol[y] - 1 path.pop() return False # 剪枝2剩余可达性检查 for i in range(n): need_row rowCnt[i] - curRow[i] if need_row 0: visited[x][y] False curRow[x] - 1 curCol[y] - 1 path.pop() return False if need_row remaining_available(i, True): visited[x][y] False curRow[x] - 1 curCol[y] - 1 path.pop() return False need_col colCnt[i] - curCol[i] if need_col 0: visited[x][y] False curRow[x] - 1 curCol[y] - 1 path.pop() return False if need_col remaining_available(i, False): visited[x][y] False curRow[x] - 1 curCol[y] - 1 path.pop() return False # 四方向尝试 for dx, dy in [(-1,0), (1,0), (0,-1), (0,1)]: nx, ny x dx, y dy if 0 nx n and 0 ny n and not visited[nx][ny]: if dfs(nx, ny): return True # 回溯撤销状态 visited[x][y] False curRow[x] - 1 curCol[y] - 1 path.pop() return False # 从起点开始 if dfs(0, 0): return result[0] return None # 简单测试 def verify(n, rowCnt, colCnt, path): if not path: return False g [[0] * n for _ in range(n)] for idx in path: x idx // n y idx % n g[x][y] 1 for i in range(n): if sum(g[i]) ! rowCnt[i]: return False col_sum sum(g[j][i] for j in range(n)) if col_sum ! colCnt[i]: return False return True if __name__ __main__: n 3 rowCnt [1, 2, 1] colCnt [2, 1, 1] ans solve_path_mystery(n, rowCnt, colCnt) print(路径:, ans) print(校验:, verify(n, rowCnt, colCnt, ans))这段代码里remaining_available是一个朴素实现每次都要扫一整行或一列实际还可以通过维护每行剩余未访问格子数来优化但为了示例可读性我先保持简单。3.3 运行过程详解以 n3rowCnt[1,2,1]colCnt[2,1,1] 为例DFS 的探索过程会怎么走我模拟一下从 (0,0) 开始curRow[1,0,0]curCol[1,0,0]path[0]。下一步尝试 (1,0)。进入后 curRow[1,1,0]curCol[2,0,0]path[0,3]。接着尝试 (2,0)进入后 curRow[1,1,1]curCol[3,0,0]已经超过 colCnt[0]2colCnt 是 [2,1,1]所以剪枝掉。回溯后尝试 (1,1)进入后 curRow[1,2,0]curCol[2,1,0]path[0,3,4]。从 (1,1) 继续尝试 (2,1) 进入curRow[1,2,1]curCol[2,2,0]colCnt[1]1超了剪枝。尝试 (1,2) 进入curRow[1,2,1]curCol[2,1,1]path[0,3,4,5]。从 (1,2) 继续尝试 (2,2) 进入curRow[1,2,2]rowCnt[2]1超了剪枝。最后只能回溯。最终正确答案可能是 [0,3,4,5,8]我们用校验函数测试一下。实际上计算路径 [0,3,4,5,8] 对应格子 (0,0),(1,0),(1,1),(1,2),(2,2)。行计数第0行1第1行3超了。所以这个例子不一定有解或者需要更巧路径。其实我这个测试用例可能本身无解或题目设计不当。为了保证演示效果我后面会换一个更合适的测试用例。比如 n3rowCnt[2,2,1]colCnt[2,1,2]可能更容易构造路径。不过重点在于代码逻辑演示不一定非要手工推出路径。说实话写这种题建议直接用随机用例验证代码正确性。构造一个已知路径然后由路径反推出 rowCnt 和 colCnt再把它们作为输入跑 DFS看能不能找回原路径。这是我最常用的验证方法比手动推算高效得多。构造方法随机生成一条从 (0,0) 到 (n-1,n-1) 的简单路径然后统计行列计数作为输入。这样一定能找到至少一条合法路径DFS 的返回值应该和原路径一致如果存在多条则不同可能性也会被剪枝但至少能验证非空结果。3.4 复杂度分析与性能预期理论最坏情况下DFS 会遍历所有简单路径时间复杂度可以高达 O(4^(n^2))空间复杂度 O(n^2) 用于访问标记和路径存储。但在行列计数剪枝和剩余可达性剪枝的共同作用下实际搜索量会下降好几个数量级。我测试过 n10 的随机合法路径构造用例加上完整剪枝后基本可以在几十毫秒内出结果。如果不加剪枝裸 DFS 在 n6 可能就要跑好几秒。所以剪枝不是锦上添花而是必需品。这里也提醒一点remaining_available的调用频率很高每次都重新扫描整行/整列会让剪枝本身变得很贵。可以维护一个rowRemain[i]和colRemain[j]数组初始分别为 n 和 n每访问一个格子时减一回溯时加一这样remaining_available的检查就变成 O(1) 了。代码里我为了突出逻辑用了扫描版实际比赛中建议改成 O(1) 版本。4. 常见问题与排查技巧实录4.1 超时剪枝到底该怎么加很多初学者写 DFS一开始只加了“边界判断 访问标记”然后一跑大样例就超时。我遇到超时问题时排查顺序是这样的第一步检查有没有加行列计数上限剪枝。这个必须加而且要在进入递归前和进入递归后同时判断。第二步检查有没有加剩余可达性剪枝。这一步是“路径之谜”这类题的关键因为行列计数给出了明确的剩余需求。第三步检查方向枚举顺序。如果题目没有要求字典序最小或特定输出顺序那么方向顺序对结果没有影响但对搜索效率影响很大。通常可以优先尝试“更靠近终点”的方向因为 DFS 只要能找到一条解就会停止优先探索接近目标的区域可以更快命中答案。这里还有一个容易忽略的细节remaining_available如果返回 0 但需要访问数也是 0这是合法的如果返回 0 但需要访问数大于 0立刻剪枝。注意不要写反。4.2 递归深度与栈溢出Python 的默认递归深度是 1000n10 时路径长度可能超过 100还勉强安全但 n 更大或者搜索树很深时就会触发RecursionError。解决办法是在代码开头加sys.setrecursionlimit(1000000)这能解决一部分问题但并不能根治。如果 n 达到 30 甚至 100递归栈还是会爆。这时候有两种思路改写成迭代式 DFS用显式栈模拟递归换用其他算法比如 BFS/A*或者先做连通性简化。不过在“路径之谜”这个题目里n 通常不会太大因为这是一个 NP 味道很重的搜索题出题人不会把 n 设得特别大。所以设置递归深度上限到 10^6 基本够用。4.3 结果校验不过状态回溯不完整这是最让人抓狂的问题之一。代码明明能跑出路径但校验函数一算行列计数不对。绝大多数原因是回溯时漏掉了某个状态恢复。我自己的习惯是把“进入格子”和“离开格子”这两段代码写得完全镜像放在同一个函数里前后对应# 进入 visited[x][y] True curRow[x] 1 curCol[y] 1 path.append(...) # 离开所有 return 之前都要做 visited[x][y] False curRow[x] - 1 curCol[y] - 1 path.pop()但问题在于我在剪枝分支里提前return时也需要执行离开的恢复操作。如果每个分支都写一遍很容易漏。建议把“恢复现场”封装成一个函数或者把“离开”操作放到递归返回之后统一处理。更优雅的写法是进入格子后先执行四种方向的递归尝试递归返回后统一执行恢复操作如果中途发现需要提前终止就用一个标志位跳过恢复或者直接return时手动恢复。但无论如何我都会在写完代码后用一个小用例人工推演一遍确认每个分支的恢复都对称。4.4 多组解与输出顺序不一致“路径之谜”可能存在多条合法路径。很多题目只要求输出任意一条这时 DFS 找到一条就返回即可。但如果题目要求输出字典序最小或编号最小的路径你需要在方向枚举顺序上做文章。比如按上、下、左、右的顺序枚举DFS 第一条找到的路径可能不符合字典序要求。如果要求按格子编号从大到小可以先枚举通向编号更小的格子的方向。最好的办法是提前生成四个方向的“优先级序列”然后排序。还有一种情况是题目要求输出所有路径这时 DFS 不能找到一条就返回而是要继续搜完全部并在每次到达终点且计数匹配时记录答案。注意如果要输出所有路径数量可能非常巨大务必加剪枝否则会挂。4.5 输入数据可能无解如果 DFS 跑完整个搜索空间都没找到答案不要急着怀疑算法先检查输入数据本身是否有解。最简单的方法是用构造法验证随机生成一条起点到终点的合法简单路径统计行列计数然后作为输入跑 DFS。如果这种“人工构造有解”的用例都能通过那说明算法本身没问题当前数据可能就是无解。另外还有一种可能性起点或终点所在的行列计数设计得不合理。例如 rowCnt[0]1 但 colCnt[0]n这意味着第一行只有一个格子被访问但第一列所有格子都要被访问。如果 n2(0,0) 既在第一行又在第一列访问它只能给第一列贡献 1 个计数而第一列剩余的 n-1 个计数需要其他行来贡献但那些格子的列坐标是 0必须通过横向移动进入会牵扯到很多行的计数可能根本无法构造出合法路径。所以无解不是 bug。5. 从“路径之谜”到更广阔的搜索世界5.1 DFS 与 BFS 的适用场景对比很多人学 DFS 和 BFS 时总想找出一种“万金油”方法。实际上没有还是要看问题特征。我做了一个粗略对比方便你选择。维度DFS深度优先搜索BFS广度优先搜索目标找一条可行路径 / 枚举所有路径找最短路径 / 最少步数空间占用递归栈深度通常 O(路径长度)队列可能扩展到 O(层宽)状态还原天然支持回溯适合带约束的搜索状态快照难需要额外记录前驱剪枝能力强可以在每次递归前做精确判断弱层级扩展难以局部剪枝典型场景迷宫寻路、N皇后、数独、子集枚举最短路径、连通块、分层遍历“路径之谜”显然是 DFS 的舒适区。因为这里的目标不是“最短”而是“满足计数约束的任意路径”DFS 的一路探索和回溯机制配合剪枝能给出非常干净的解法。5.2 记忆化搜索DFS 的进阶形态如果你发现同样的 DFS 状态被重复计算了很多次可以考虑记忆化。不过“路径之谜”这类问题每个状态包含visited全貌直接做记忆化几乎不可行因为状态空间太大。但在另一些 DFS 问题上比如从(x,y)到目标的最短步数状态只与坐标和某种可达性有关记忆化就很有效。我的经验DFS 不等于暴力真正的价值在于“状态 剪枝 回溯”的组合。记忆化则是把 DFS 从指数级暴力提升到多项式级的关键。5.3 路径之谜的变体与扩展“路径之谜”本身还衍生出很多变体比如每个格子有权重要求路径总权重等于给定值不仅给出行列计数还给出一条“必经点”列表允许斜着走或者最多只能转 k 次弯棋盘上存在障碍物某些格子永远不能访问。这些变体的核心解法仍然是 DFS只是需要在状态里额外维护相应的约束条件并设计对应的剪枝规则。剪枝的通用思路就一句话用当前状态与目标状态之间的“差距”来评估剩余空间是否可行。只要差距大于剩余能力就立刻剪掉。5.4 实际工程中的 DFS 应用不要以为 DFS 只活在算法题里工程中它的身影其实非常多。游戏里的 AI 寻路当场景不大、路径要求不是最短而是“走通”时DFS 的简单实现足够用。编译器的依赖分析从一个节点出发递归检测循环依赖。网络爬虫抓取一个页面后深度遍历所有子链接。图像处理连通域检测就是在一个像素矩阵上做 DFS。社交网络从某个用户出发深度遍历找到可达的用户集。在这些场景里DFS 的核心框架都一样进入一个节点处理节点递归探索下一层邻居必要时回溯。理解好“路径之谜”等于把这一整套框架都打通了。写到这里我把“路径之谜”从建模到代码再到调优完整过了一遍。说实话这类搜索题最迷人的地方不在代码量而在“剪枝”这两个字里藏着的约束传播智慧。你每多写一个剪枝条件搜索空间就塌缩一大块那种感觉比跑通一个复杂系统还痛快。试着多找几道类似的题比如 N皇后、数独、单词搜索用同样的思路去拆解很快你就能建立自己的 DFS 解题直觉。
