★ FEATURED ARTICLE 如果你最近在整理深搜题单多半会碰到编号 6300 的 Grid Path Construction。这个标题在部分平台的内部编号里还会记成 2418但不管怎么换名字它要解决的核心问题都一样在一块可能带墙的矩形网格上从起点走到终点把所有空地恰好踩一遍构造出一条完整路径。初看像迷宫搜索实际上一旦数据规模上来朴素 DFS 立刻会暴露真实面目要么几十分钟跑不出结果要么直接爆栈。这道题非常适合用来检验一个人对搜索剪枝的理解程度。下面我会从题面拆解开始把状态设计、剪枝原理、工程实现和调试踩坑完整过一遍希望对正在啃深搜的朋友有帮助。1. 读懂题面Grid Path Construction 到底在考什么1.1 三种常见设定先别急着写码先交代一个容易让人困惑的地方无论是在训练系统刷到的 6300还是记录成 2418 的原题版本题面描述在细节上会有一点差别但骨架基本一致——给定一个 R 行 C 列的网格图其中一部分格子是墙另一部分是可走的空地另有起点坐标和终点坐标要求输出一条从起点到终点的路径并且这条路径必须覆盖所有空地、每个空地恰好经过一次。如果找不到这样的路径按要求输出无解。这类题具体到不同平台会有三种常见变体。第一种起点终点固定输出坐标序列这也是最标准的考法也就是 6300 在我印象里的主要形态。第二种起点固定但终点不固定只要能构造出一条覆盖所有空地的路径就行。第三种最宽松起点终点都可以自己选只问是否能做一笔画覆盖。这三种变体的底层算法是同一套 DFS只是终止条件不同改起来也就是一两行的事。数据范围是另一个关键变量。小数据通常是 4×5、5×5这种规模暴搜都能过但一旦到 8×8 或者 12×16空地数量可能超过 100问题就从能不能写深搜变成了深搜能不能活下来。这里的核心考点不是你知道递归里有个 visited 数组而是三件事你能不能把状态定义干净能不能在递归早期识别出不可恢复的死路以及能不能给你的 DFS 选一个足够聪明的搜索顺序。理解到这一层题面才算真正读完。1.2 状态空间账本为什么朴素 DFS 必挂先说一个最直观的数字账。假设一个 8×8 的全空网格从 (0,0) 出发到 (7,7) 结束一共 64 个空地。搜索路径时除了最后几步每个中间位置平均有 2 到 4 个可扩展方向取个保守的平均值 3那么整棵搜索树的分支量级大约是 3 的 64 次方。这个数字是 3.4×10^30 左右哪怕每个分支只耗费 1 纳秒总时间也有 10^21 秒量级远远超过宇宙年龄。有人会说DFS 又不是把所有路径都枚举完走到一半就会撞墙。说得对但你要理解撞墙回溯也意味着搜索树内部节点的数量同样惊人。就算去掉九成九的无用分支剩下的搜索量仍在指数级别。这也是我在第 3 节要重点讲剪枝的原因剪枝的收益不是线性的而是随着层数指数叠加。你在某一层砍掉 99% 的分支到第 64 层时作用相当于把一个天文数字压缩成零。所以我可以直接给一个结论这类题如果你写出来的代码没有包含任何结构性剪枝那在中小数据上大概率能过在接近上限的数据上基本会超时。这道题的存在意义就是逼你去理解深搜的真正瓶颈不是递归写法而是搜索空间的剪枝力度。1.3 回到图论网格路径就是网格上的哈密顿路径这道题还有一层更理论的外衣。把每个空地当成图上的一个顶点相邻空地之间连一条边题目就等价于在一个网格图中找一条哈密顿路径——一条经过每个顶点恰好一次的路径。这个视角的价值在于网格图不是一般图它是二分图。具体说把坐标 (xy) 的奇偶性作为颜色标记你会发现每个格子的邻居颜色都与它自己相反。哈密顿路径在二分图上有一个非常强的性质路径每走一步颜色必然翻转所以路径经过多少步以及起点和终点的颜色分布之间存在固定的奇偶关系。这个性质不是装饰它是第 3 节里第一个剪枝的理论基础。后面写代码时你会经常用到一句话如果剩余步数的奇偶性和当前位置到终点的曼哈顿距离奇偶性不一致那这一整棵子树都不用搜了。2. DFS 的骨架实现状态、转移、方向序2.1 visited 数组、路径栈、步数计数器三者怎么配合先谈状态表示。这道题不需要搞什么复杂哈希三块信息足够一块二维 visited 数组表示哪些格子已经被路径占用一个当前坐标 (x, y)一个已经走过的格子数 step。其中墙可以直接预先把 visited 标记成 true这样边界和墙体检查可以合并减少一层逻辑分支省得每次递归都单独判断墙。路径输出用栈来维护。如果题目要求输出坐标序列就维护一个 vector 或 list每次进入新格子时 push回溯时 pop。这样递归返回时路径栈自然回到上一个状态不需要做昂贵的拷贝。这里踩过坑的朋友应该深有体会有人图省事用字符串拼接来记录方向结果每次分支拷贝一整串字符回溯时要截断、要反转性能直接崩掉一小截。坐标栈的做法最直接无论是 Python 的 list 还是 C 的 vector都是 O(1) 的 push/pop没有任何多余的拷贝。step 的初始值有讲究。起点已经占了一个格子所以从起点进入 DFS 时 step 通常从 1 开始而不是 0。当 step 等于总空地数 total 时路径覆盖完毕。判断终点的时机也要注意常见错误是在每次递归入口判断当前坐标等于终点但应该判断是否覆盖完所有空地并且恰好站在终点。这两个条件缺一个都不算成功。2.2 方向顺序小改动大差距在递归函数里四个方向的枚举顺序看起来微不足道但它经常决定了搜索从几十毫秒变成超时。原因很简单DFS 的早期决策决定了整棵搜索树的形状如果你总是优先朝向容易走死的一侧搜索就会在大量注定无解的分支里反复扎进去又回溯出来。一个经过验证的实用做法是在循环里按距离终点更近优先的顺序来枚举方向。比如当前在 (x, y)终点在 (tx, ty)把四个方向按曼哈顿距离增量从小到大排个序距离增量小说明这步是在往终点方向靠大概率是能解路径的方向。这个排序本身只有 O(1) 开销但效果却经常非常惊人。我自己实测 10×10 网格时固定按上右下左枚举有些随机墙布局要跑几十秒甚至跑不出来改成动态排序后一组同样布局的求解时间直接降到几百毫秒。方向序本身不是剪枝但它是搜索效率的第一块垫脚石。2.3 为什么这一题不要想记忆化有些稍微熟悉搜索优化的朋友会问能不能用记忆化把当前坐标 visited 状态缓存起来避免重复状态理论上说得通但实现上基本行不通。问题出在 visited 集合的状态空间本身。一片 8×8 的网格能用一条路径访问的中间状态数量已经不是 2 的 64 次方那么简单了实际上会更大。就算压缩成位掩码64 个格子的状态需要 64 位整数哈希一个 64 位的位掩码固然快但状态数量爆炸导致内存根本无法支撑。更重要的是这类构造型搜索最重要的优化不是去重而是提前砍掉不可能完成目标的分支。剪枝是主动的记忆化是被动的两者完全不是一个量级。在这道题里我们应当把全部精力放在剪枝上。具体怎么剪我放在第 3 节详细展开。2.4 剪枝梯队先定思路再写代码我写这一类搜索题习惯先在心里把剪枝分成三个梯队然后再落代码。第一梯队是零成本剪枝。所谓零成本就是只需要几次整数运算就能完成判断比如奇偶性剪枝曼哈顿距离判断当前点是否为孤立点。这类剪枝适合在每次递归入口无条件执行。第二梯队是局部剪枝它只需要扫描当前格子的四邻域或两三层邻居成本是常数级每层执行也不会拖慢太多。第三梯队是全局剪枝比如剩余未访问格子的连通性检查它需要跑一次 BFS 或 DFS扫描整张图成本很高所以只在特定层次、特定间隔或搜索接近尾声时才执行。顺序为什么重要如果你把昂贵的全局剪枝放在每个节点都跑搜索树的每个节点都要多花 O(VE) 的时间哪怕剪枝很有效前期收益也可能被时间成本吃光。正确的思路是便宜的剪枝先上贵的剪枝只在关键时刻上。后面第 4 节调参实录里我还会再讲一次这个顺序对运行时间的直接影响。3. 真正拉开差距的三个关键剪枝的原理与代码3.1 二分图奇偶性O(1) 的定理级剪枝第一个剪枝来自前面提到的二分图性质。你把网格按 (xy)%2 染成黑白两色合法路径每走一步颜色必然翻转。如果一共要走 N 步也就是还剩下 total-step 步当前位置到终点的曼哈顿距离是 d那么 d 的奇偶性和 N 的奇偶性必须一致。因为路径至少需要 d 步才能到终点而如果总共要走 N 步那么 N 减去 d 必须是偶数多出来的步数只能以一对一对的往返形式出现否则终点颜色会对不上。写成代码极其简单if ((abs(x - tx) abs(y - ty)) 1) ! ((total - step) 1): return False这个判断是 O(1) 的放在每层递归最前面。它在大部分情况下都是通过但在某些看似有很多扩展方向的节点它会直接告诉你这棵子树就算走到底也不可能到达终点。这个剪枝能砍掉大约一半的无效分支而且几乎不花时间属于教科书级别的性价比。3.2 死胡同邻居剪枝识别局部结构里的绝路第二类剪枝是处理孤立点或死胡同邻居。每当我们准备从当前格 X 走到下一个未访问格 N 时可以提前看看 N 还有没有其他未访问邻居。如果 N 的空闲邻居数量是 0而 N 又不是终点那走进 N 就是死路一条进去之后没有任何未访问格子可以接着走除非路径正好要在这一步结束。所以遇到这种情况下我们应该直接跳过这个方向。这个判断其实是对称的一个格子如果只剩一个可以进入的口子那它在路径上必然是最后一个被访问的点。理解了这一点代码就非常直观for dx, dy in dirs: nx, ny x dx, y dy if not inside(nx, ny) or visited[nx][ny]: continue if (nx, ny) ! (tx, ty) and not free_neighbors(nx, ny): continue visited[nx][ny] True ...这里的 free_neighbors(nx, ny) 返回的是 (nx, ny) 在四个方向上未访问的邻居列表。小心点别把当前格算进去因为当前格已经被 visited 标记了。这个剪枝的成本很低只需要扫一轮四邻域但能挡住相当多的短路。尤其是当你离终点还很远时一旦某一个候选方向是一根慢慢变窄的死胡同它能帮你及时转向。如果还想做更深一层可以检查当前格的某个邻居是一个只有当前格这个邻居的死端那么你必须立刻走到那个邻居。这属于强制性移动剪枝本质上和孤立点是同一个思想只是判断的视角反过来。这种增强版剪枝在墙布局比较复杂的网格上效果更明显但实现时要小心处理多个必须移动邻居冲突的情况代码容易绕晕我一般只在板子题里加死胡同跳过这一层速度已经够用。3.3 剩余连通性检查最贵也最猛的全局剪枝第三个剪枝是全局连通性检查。它的思想是路径每前进一步都会从剩余未访问的格子里拿走一个点。如果当前剩余的未访问格子集合是不连通的那么后续路径绝对不可能把它们全部串起来因为这需要路径在已经访问过的格子上跳跃。具体实现就是在把下一步格子标记为 visited 之后从那个新位置出发跑一次 BFS/DFS统计能到达多少个未访问格子。如果这个数量和总空地数减去已走步数不一致说明剩余区域被切成了两块立刻剪枝。def reachable_count(x, y): q deque([(x, y)]) seen {(x, y)} while q: cx, cy q.popleft() for dx, dy in ((-1,0),(1,0),(0,-1),(0,1)): nx, ny cxdx, cydy if inside(nx, ny) and not visited[nx][ny] and (nx, ny) not in seen: seen.add((nx, ny)) q.append((nx, ny)) return len(seen)这个剪枝非常强大它能抓住局部检查捕捉不到的大块死局比如你把搜索路径走成了一个封闭环路把一大片空地关在墙外这种结构要回溯非常深的层级才能发现。但它也有代价每调用一次就要跑一遍 O(VE) 的 BFS。如果每一层递归都跑搜索树的节点数本身是指数级的全局扫描会让每个节点都背上巨大的常数。怎么平衡我的做法是隔几层做一次比如 step % 4 0 时才触发。还有一种更聪明的触发方式只在当前格子的空闲邻居数小于等于 2 时做因为邻居数少意味着剩余区域可能被路径夹住这时连通性风险最大。实测下来命中率很高比固定间隔更有效。3.4 带着四层剪枝的完整参考实现下面给一份可以直接跑的 Python 参考实现它包含了我上面讲到的方向排序、奇偶性剪枝、死胡同剪枝和间隔性连通性检查。代码中的核心逻辑你直接抄下来改一下输入解析就能套到自己的题单里。import sys from collections import deque sys.setrecursionlimit(1 25) def solve_grid_path(R, C, start, end, walls): visited [[False] * C for _ in range(R)] for x, y in walls: visited[x][y] True sx, sy start tx, ty end total R * C - len(walls) visited[sx][sy] True path [(sx, sy)] def inside(x, y): return 0 x R and 0 y C def free_neighbors(x, y): res [] for dx, dy in ((-1, 0), (1, 0), (0, -1), (0, 1)): nx, ny x dx, y dy if inside(nx, ny) and not visited[nx][ny]: res.append((nx, ny)) return res def reachable_count(x, y): q deque([(x, y)]) seen {(x, y)} while q: cx, cy q.popleft() for dx, dy in ((-1, 0), (1, 0), (0, -1), (0, 1)): nx, ny cx dx, cy dy if inside(nx, ny) and not visited[nx][ny] and (nx, ny) not in seen: seen.add((nx, ny)) q.append((nx, ny)) return len(seen) def dfs(x, y, step): if step total: return (x, y) (tx, ty) # 1) 奇偶性剪枝 if ((abs(x - tx) abs(y - ty)) 1) ! ((total - step) 1): return False # 2) 方向排序优先靠近终点 dirs [(-1, 0), (1, 0), (0, -1), (0, 1)] dirs.sort(keylambda d: abs(x d[0] - tx) abs(y d[1] - ty)) for dx, dy in dirs: nx, ny x dx, y dy if not inside(nx, ny) or visited[nx][ny]: continue # 3) 死胡同邻居剪枝 if (nx, ny) ! (tx, ty) and not free_neighbors(nx, ny): continue visited[nx][ny] True path.append((nx, ny)) # 4) 全局连通性剪枝隔 2 层检查一次 if step % 2 0 and reachable_count(nx, ny) ! total - step - 1: path.pop() visited[nx][ny] False continue if dfs(nx, ny, step 1): return True path.pop() visited[nx][ny] False return False if dfs(sx, sy, 1): return path return None if __name__ __main__: # 示例用法4x5 网格起点 (0,0)终点 (3,4)无墙 result solve_grid_path(4, 5, (0, 0), (3, 4), []) if result: print(OK, len(result)) print(result) else: print(NO PATH)注意一个细节在这个实现里墙也被标记进 visited所以 free_neighbors 不会把墙当邻居算省掉了一次单独的墙判断。这是我在工程上很喜欢的写法会让递归内部的逻辑更干净。如果你想用 C 刷这题思路完全一样。下面是一个浓缩版本只包含奇偶性和死胡同剪枝适合数据规模中等的情况#include bits/stdc.h using namespace std; int R, C, sx, sy, tx, ty, total; bool wall[25][25], vis[25][25]; int dx[4] {1, -1, 0, 0}; int dy[4] {0, 0, 1, -1}; vectorpairint, int path; bool inside(int x, int y) { return x 0 x R y 0 y C; } bool dfs(int x, int y, int step) { if (step total) return x tx y ty; // 奇偶性剪枝 if ((abs(x - tx) abs(y - ty)) % 2 ! (total - step) % 2) return false; for (int k 0; k 4; k) { int nx x dx[k], ny y dy[k]; if (!inside(nx, ny) || vis[nx][ny]) continue; // 死胡同邻居剪枝 int cnt 0; for (int l 0; l 4; l) { int ux nx dx[l], uy ny dy[l]; if (inside(ux, uy) !vis[ux][uy]) cnt; } if ((nx ! tx || ny ! ty) cnt 0) continue; vis[nx][ny] 1; path.push_back({nx, ny}); if (dfs(nx, ny, step 1)) return true; path.pop_back(); vis[nx][ny] 0; } return false; }C 版本省略了方向排序和连通性检查因为很多训练系统的数据范围用这两层剪枝已经能过。当然如果你自己测试时遇到更大的网格把 Python 版里的排序和连通性检查搬过来即可核心逻辑完全通用。4. 调试实录那些让人抓狂的坑与数据验证4.1 九类常见错误速查表这类搜索题的错误通常不在算法上而在实现细节里。我整理了一份自己踩过、也看过别人踩的速查表你对照着检查自己的代码会快很多。症状常见原因对策多组数据时结果飘忽visited 或 path 没重置干净每组数据开始前重新初始化全局数组起点或终点被当成墙输入解析时把墙集合误判在填充 wall 时跳过起点终点递归栈溢出数据规模大递归层数深Python 用 setrecursionlimitC 加大栈空间结果路径少一个点或多一个点step 初始值或 total 计算错误在入口打印 step 与 total 做单测明明可行却报无解剪枝条件写反误杀正解先关剪枝跑小数据对拍运行极慢方向顺序固定且无局部剪枝加方向排序和死胡同剪枝路径坐标顺序反了push 的时机不对确认进入新格时 push回溯返回时 pop终点判断提前在中间点就返回成功改为 step total 且坐标等于终点边界数组越界只判断了 x R漏了 x 0所有越界判断统一写成 not (0 x R)这些错误里我最想单独拎出来说的是剪枝误杀正解。它比超时更隐蔽因为程序会正常结束还会有条理地输出无解让你以为网格本身就没有解。遇到这种情况第一反应不是改剪枝而是先把所有剪枝关掉在小网格上跑一遍暴力搜索确认题目设计确实有解。两相对拍再逐步把剪枝加回来找出是哪个判断写岔了。4.2 剪枝开关实测一次 10×10 死局的调参过程我在本地做过一轮剪枝对拍用一个 10×10 的网格墙的分布故意设计成一个弯曲的窄通道要求从左上角走到右下角。这种布局有一个特点表面上存在多条可达路径但多数走到一半就发现剩余区域被自己切成两段根本连不通。第一版代码只写了 visited 和基础 DFS方向顺序固定没有任何剪枝。结果我盯了屏幕整整两分钟它还在跑最终只能手动中断。第二版加了奇偶性剪枝。运行时间从两分钟降到四十多秒但依然不能接受。第三版加了死胡同邻居剪枝。这次快了很多降到几秒量级但偶尔有几个随机墙布局仍然会卡住。第四版加上了间隔性连通性检查并且把方向顺序改成动态排序。同样是那一组布局最快的一次只用了两百多毫秒。差距大到我不小心关掉了剪枝又跑了一遍确认没搞错测试数据。调参途中我还试过把连通性检查改成每层都跑结果时间反而翻了几倍。原因是早期层级的搜索树节点太多每次 BFS 的固定成本被放大得很厉害。后来改成 step % 4 0 时触发速度才稳定下来。这也验证了剪枝梯队的思想昂贵剪枝必须放在合适的时机而不是越频繁越好。4.3 对拍与压力测试怎么验证剪枝没砍掉正解给搜索代码验正确性最可靠的方法不是目测而是对拍。写一个完全不剪枝的暴搜在小网格上跑所有可能解再跑你的剪枝版本两者输出必须完全一致。小网格比如 4×4、5×5 的规模暴搜都能在几毫秒内完成足够做大量样例。具体步骤是用随机数生成器批量造网格。每个网格随机放置 10% 到 30% 的墙起点终点随机挑两个空地。然后暴力版和剪枝版分别跑比对判定结果。如果输出路径还要比对路径长度、起点、终点、覆盖格子的集合。随机样例跑到几百组以上之后正确性基本就有保障了。这一步不要偷懒。剪枝写得越狠误杀风险越大越需要靠对拍来兜底。我见过很多竞赛里因为剪枝写错明明是正解却输出无解一整道题挂零分的情况。宁可多花二十分钟对拍也不要带着一颗定时炸弹去交代码。5. 这类题能带走什么经验5.1 构造型搜索题的通用套路做完 Grid Path Construction你会发现自己以后遇到一大半搜索题都会自带免疫。我的体会是这类构造一条满足条件的路径/序列的题目核心套路可以概括成四句话。第一句状态别贪多够用就行。visited 加坐标加步数绝大多数移动类题目都能覆盖。第二句能用定理性质做剪枝就优先用。网格题的奇偶性、二分图、奇偶染色数独的宫格约束N 皇后的对角线约束这些结构性信息往往是最强也最省事的剪枝。第三句局部检查常开全局检查按节奏开。死胡同邻居这种 O(1) 检查每层都跑没问题连通性这种 O(VE) 的检查千万别滥用。第四句搜索顺序永远值得调一调很多时候换个排序性能就是两个世界。5.2 相似题与后续扩展方向这类套路能直接迁移的题其实有一大片。最像的是各类棋盘上的覆盖路径问题比如骑士巡游在棋盘上用骑士的走法访问所有格子恰好一次。它同样是哈密顿路径同样是 DFS 加剪枝奇偶性检查换成骑士步数的奇偶分析孤立点检查换成骑士可达性。理解了今天这一题骑士巡游你就能无痛上手。另一个相似方向是数独求解。数独里每个空格填哪个数字本质上也是在构造一条满足约束的搜索路径而数独最著名的技巧——唯一候选数、隐性唯一数——本质上就是局部剪枝的变体。你在 Grid Path Construction 里练出的在递归前先识别死路的思维到数独里其实就是扫描候选数是否存在唯一解。再往上走一步还可以把这个问题理解成一种规划问题。如果你想求的不是任意一条路径而是一条最短路径或最接近某种目标的路径DFS 就不够看了需要换成 A* 或迭代加深。但 A* 的启发式设计和连通性检查之间共享的仍然是如何度量剩余问题的难度这个核心思想。5.3 最后分享一个调试小技巧文章末尾我想分享一个自己调试搜索题时一直在用的小技巧在 DFS 入口打印缩进过的调用栈。说白了就是在函数开头根据 step 打印若干空格再打印坐标和当前层数。print( * step, f({x},{y}) step{step})这样在跑小数据时你能直观地看到回溯发生在哪些坐标上哪些子树被反复进出。剪枝加错的时候这个输出会迅速暴露问题比如某个坐标明明应该被访问却根本不在递归日志里说明它在更早的节点就被错误跳过了。等你确认逻辑正确、性能达标之后记得把这些打印全删掉不然提交的时候输出会被污染评测直接判格式错误。这种开着日志调搜索的习惯比单纯靠眼睛看代码要高效得多。每次和人讨论深搜题我都建议先花五分钟把调用日志打开再看数据很多莫名其妙的 bug 其实一眼就能定位。这一题刷完你收获的不只是一个 AC而是一整套面对搜索空间爆炸的分析框架。下次再遇到类似的深搜题我相信你很快就能判断出该剪哪里、什么时候剪、用什么代价剪。
阅读完成 · 觉得有帮助？
