我们写过网格DFS数岛屿把回溯搬上了二维棋盘。今天把两者合体网格回溯。好消息是——你其实已经会了。把那套网格DFS模板拿出来补上一个撤销动作就是今天的主题。先看两段骨架有多像为什么岛屿可以永久标记、单词搜索必须还原这是“普通DFS”与“回溯”的分界线岛屿问题问的是“这个格子属于哪个连通块”。访问过一次归属就确定了永久沉没是正确且必要的。单词搜索问的是“存不存在一条合法路径”。格子A在路径1里被用过了但另一条完全不同的路径仍然可以用它——限制只作用于“当前这条路径”。所以用完必须还回去。一句话判据如果“访问过”这件事对整个问题永久成立 → 普通DFS如果只对当前路径成立 → 回溯要撤销。这条判据是今天全篇的钥匙。 题目速览 LeetCode 7930 秒读懂题目1单词搜索LC.79在m × n字符网格中判断word是否存在。单词按字母顺序、通过上下左右相邻格子构成同一格不能重复使用。示例网格含ABCCED→trueABCB→falseB不够约束m,n ≤ 6word长度 ≤ 15。题目2解数独LC.37作拓展讲填充空格使每行、每列、每宫都是1-9不重复。 核心思路四方向 原地标记 三处剪枝3.1 骨架三个固定动作越界判断0 r m and 0 c n四方向扩展DIRS [(1,0), (-1,0), (0,1), (0,-1)]写成常量数组循环调dfs就地标记把访问过的格子改成#回溯时改回来为什么用原地标记而不是visited数组两个理由省空间visited是O(m·n)额外数组原地标记是O(1)额外判定合并原本要查两件事“访问过吗” “字符匹配吗”原地标记后一次比较搞定——因为#不可能等于任何字母代价只有一个必须记得改回来。这是本题第一号bug。3.2 剪枝三处按性价比排序剪枝一最便宜首字符不匹配直接跳过起点forrinrange(m):forcinrange(n):ifboard[r][c]!word[0]:continue# 起点都不匹配白跑ifdfs(r,c,0):returnTrue剪枝二性价比最高字符频次预处理统计board里每个字符出现次数word里每个字符需要次数——只要有一个字符棋盘里不够直接return False一次递归都不用进。实测5×5全A棋盘查A × 26棋盘只有25个A版本递归调用次数耗时无频次剪枝12,241,6932.479s有频次剪枝00.000052s快了约47,000 倍代价只是两个CounterO(m·n) 预处理。剪枝三必须的找到即层层短路dfs返回bool一旦某个方向返回True立刻return True向上传递不要继续遍历其余方向。3.3 拓展解数独——返回值是bool的“全填完才算解”LC.79单词搜索LC.37解数独决策单位一条路径下一步走哪格一个空格填1~9分支数≤ 4实际 ≤3不能回头≤ 9成功条件匹配到最后一位即成功所有空格填完才成功返回值bool找到即停bool找到即停判重原地标记#三个boolean[9][9]撤销改回原字符三个集合remove数独的关键优化MRV启发式——每步优先选候选数字最少的空格。原因很直觉候选最少的格子最容易“暴露矛盾”早失败早回头。实测经典例题51个空格版本回溯节点数耗时按行列顺序填4,2090.00267sMRV520.00017s节点少81倍快15.7倍——同一份骨架只换“先填谁”的顺序。️ 图解算法手把手走一遍LC.79走出“ABCCED”关键点路径里C用了两次但它们是两个不同格子——这正是“同一单元格不能重复使用”的准确含义。递归栈与原地标记的逐帧快照帧递归调用匹配动作被标记成#的格子返回值1dfs(0,0,0)AA✅标记 (0,0){(0,0)}—2dfs(0,1,1)BB✅标记 (0,1) (0,1)—3dfs(0,2,2)CC✅标记 (0,2) (0,2)—4dfs(1,2,3)CC✅标记 (1,2) (1,2)—5dfs(2,2,4)EE✅标记 (2,2) (2,2)—6dfs(2,1,5)DD✅标记 (2,1) (2,1)—7dfs(_,_,6)ilen——True层层短路如果不还原会怎样假设word ABCCEX第6帧失败后要回退到(2,2)继续尝试如果(2,1)的D没被还回去后续任何路径走到(2,1)都会看到#而永远匹配不上——一次忘记还原整张棋盘就废了。为什么“不能回头”让分支数从4降到3(r,c) ↑ ← [当前格] → ↓ 从 (r,c) 出发有4个邻居但其中一个是刚才来的那格—— 它此刻正被标记为#字符必定不匹配所以自动被剪掉。 → 有效分支 ≤ 3这就是复杂度里3^L的来源。LC.37 解数独宫号公式box_id (r // 3) * 3 (c // 3) ┌─────┬─────┬─────┐ │ 0 │ 1 │ 2 │ ├─────┼─────┼─────┤ │ 3 │ 4 │ 5 │ ├─────┼─────┼─────┤ │ 6 │ 7 │ 8 │ └─────┴─────┴─────┘ 代码实现Python JavaPython版fromcollectionsimportCounterclassSolution:# LC.79 单词搜索 defexist(self,board:List[List[str]],word:str)-bool:m,nlen(board),len(board[0])# 剪枝②字符频次预处理board_cntCounter(chforrowinboardforchinrow)word_cntCounter(word)forch,needinword_cnt.items():ifboard_cnt[ch]need:returnFalseDIRS((1,0),(-1,0),(0,1),(0,-1))defdfs(r,c,i):ifilen(word):# 全部匹配完 成功returnTrueifnot(0rmand0cn):# 边界returnFalseifboard[r][c]!word[i]:# 字符不匹配# 也在这被拦returnFalseboard[r][c]## 原地标记fordr,dcinDIRS:ifdfs(rdr,cdc,i1):# 找到即层层短路returnTrueboard[r][c]word[i]# 撤销必须改回来returnFalseforrinrange(m):# 剪枝①起点不匹配直接跳过forcinrange(n):ifboard[r][c]word[0]anddfs(r,c,0):returnTruereturnFalse# LC.37 解数独MRV启发式 defsolveSudoku(self,board:List[List[str]])-None:rows[set()for_inrange(9)]cols[set()for_inrange(9)]boxes[set()for_inrange(9)]blanks[]forrinrange(9):forcinrange(9):vboard[r][c]ifv.:blanks.append((r,c))else:rows[r].add(v);cols[c].add(v);boxes[(r//3)*3c//3].add(v)defcandidates(r,c):b(r//3)*3c//3return[vforvin123456789ifvnotinrows[r]andvnotincols[c]andvnotinboxes[b]]defbacktrack(k):ifklen(blanks):returnTrue# MRV挑候选最少的空格先填best,best_candk,Noneforidxinrange(k,len(blanks)):r,cblanks[idx]candcandidates(r,c)ifbest_candisNoneorlen(cand)len(best_cand):best,best_candidx,candiflen(cand)1:breakblanks[k],blanks[best]blanks[best],blanks[k]r,cblanks[k]b(r//3)*3c//3forvinbest_cand:board[r][c]v rows[r].add(v);cols[c].add(v);boxes[b].add(v)ifbacktrack(k1):returnTrueboard[r][c].rows[r].discard(v);cols[c].discard(v);boxes[b].discard(v)returnFalsebacktrack(0)Java版classWordSearchSolution{privatestaticfinalint[][]DIRS{{1,0},{-1,0},{0,1},{0,-1}};privatechar[][]board;privateintm,n;privateStringword;publicbooleanexist(char[][]board,Stringword){this.boardboard;this.mboard.length;this.nboard[0].length;this.wordword;// 剪枝②字符频次预处理int[]cntnewint[128];for(char[]row:board)for(charch:row)cnt[ch];for(charch:word.toCharArray()){if(--cnt[ch]0)returnfalse;}for(intr0;rm;r){for(intc0;cn;c){if(board[r][c]word.charAt(0)dfs(r,c,0))returntrue;}}returnfalse;}privatebooleandfs(intr,intc,inti){if(iword.length())returntrue;if(r0||rm||c0||cn)returnfalse;if(board[r][c]!word.charAt(i))returnfalse;board[r][c]#;// 原地标记for(int[]d:DIRS){if(dfs(rd[0],cd[1],i1))returntrue;// 找到即短路}board[r][c]word.charAt(i);// 撤销returnfalse;}}⚠️防坑提醒必看原地标记的哨兵字符要选输入中不可能出现的用#很安全。撤销必须写在所有方向都失败之后。“找到即短路”分支里可以故意不还原——因为函数即将返回board不再被使用。但若题目改成“找出所有路径”就必须还原。数独的boxes[(r/3)*3 c/3]别写错成(r/3) (c/3)。实测数据本机运行LC.79 官方三例用例结果递归调用次数备注ABCCEDtrue14起点(0,0)一次命中SEEtrue12第一个S走不通换 (1,3) 成功ABCBfalse0频次剪枝直接否频次剪枝的威力极限压测场景无剪枝有频次剪枝提速3×3 全A查A×102,621次0次瞬时4×4 全A查A×17114,064次 / 0.022s0次/ 0.000030s≈ 733×5×5 全A查A×2612,241,693次 /2.479s0次/ 0.000052s≈ 47,000ד存在”与“拼不出”的对比用例结果递归调用次数BEACADDDDB真实存在true85AADDDBBCED频次够但拼不出false1,272“拼不出”比“拼得出”贵15倍——因为失败要穷尽所有可能路径才能下结论。LC.37 解数独51个空格版本回溯节点数耗时按行列顺序填4,2090.00267sMRV520.00017s⏱️ 复杂度分析面试必问题目时间空间LC.79 单词搜索O(m·n·3ᴸ)L word长度O(L)递归栈原地标记O(1)额外LC.37 解数独上界O(9ᴷ)实际远小于此O(K)为什么是3ᴸ不是4ᴸ4个邻居里有1个是来路已被标记#必然不匹配。说3ᴸ能体现你想过“不能回头”这件事。一条通用经验网格回溯的时间 起点数 × 分支因子^深度。优化就砍这三个数中的任何一个。 举一反三7道高频变体题题目变化思路要点LC.212 单词搜索II多个单词一次找Trie前缀树 一次DFS前缀级剪枝LC.130 被围绕的区域找“不被边界连通”的O从边界反向DFS标记连边界的OLC.200 岛屿数量数连通块普通DFS标记后不还原LC.417 太平洋大西洋水流双向可达从两条边界各做一次反向DFS取交集LC.1219 黄金矿工网格上求最大收益路径回溯 求最大值不短路走完全部LC.980 不同路径 III走遍所有格子恰好一次回溯 bitmask记已访问LC.51 N皇后二维但不是网格路径按行降维 常数判对角线 面试追问模拟提前准备惊艳全场Q1为什么用原地标记而不是visited数组①省空间O(1)额外 vs O(m·n)②代码更短把“是否访问过”和“字符是否匹配”两次判断合并成一次字符比较③缓存友好。代价是必须记得还原。如果board不允许被修改就老老实实用visited。Q2多单词查询怎么优化单个单词用LC.79的DFS是O(m·n·3ᴸ)但查W个单词逐个跑就是W倍。正确做法是LC.212把所有单词建成一棵Trie然后在棋盘上做一次DFS。DFS过程中同步在Trie上走当前字符在Trie里走不通就剪枝前缀级剪枝比频次剪枝还强走到单词结尾就收集答案并从Trie删除该分支。复杂度从O(W · m·n·3ᴸ)降到O(m·n·3ᴸ 单词总长度)。Q3还有什么剪枝空间①频次剪枝本篇性价比最高实测47,000×②首尾对称剪枝如果word反着拼起点更少就反着搜③连通性预检word相邻字符在棋盘上必须存在至少一对相邻格子④ 超长wordL m·n直接判否。Q4解数独为什么MRV快这么多因为回溯代价主要由失败的子树决定。候选最少的格子能把矛盾提前暴露填错一个唯余格立刻return false砍掉整棵子树按行列顺序填可能要填十几个才撞上矛盾。本质是改变搜索树形状也是所有 CSP 求解器的标准启发式。 实战小技巧刷题党必备口诀网格回溯 DFS 一个撤销永久标记是普通DFS临时标记才是回溯。模板四方向 边界 原地标记 找到即短路 撤销。防坑撤销写在所有方向失败之后频次剪枝别省。 实际应用场景不止是刷题拼字游戏Boggle、Wordle类路径规划走迷宫、机器人寻路图像处理连通区域标记约束求解数独、排课、排班芯片布线走线冲突检测 今日思考题LC.79的“找到即短路”分支里还原board[r][c]是必须的吗提示从“函数即将返回、board不再被使用”的角度想。但如果这是一道要返回所有路径的题比如 LC.212找所有单词答案就完全不同了——想想为什么。