企业官网建设流程全解析

我们写过网格DFS数岛屿，把回溯搬上了二维棋盘。今天把两者合体：网格回溯。

好消息是——你其实已经会了。把那套网格DFS模板拿出来，补上一个撤销动作，就是今天的主题。

先看两段骨架有多像：

为什么岛屿可以永久标记、单词搜索必须还原？这是“普通DFS”与“回溯”的分界线：

• 岛屿问题：问的是“这个格子属于哪个连通块”。访问过一次，归属就确定了，永久沉没是正确且必要的。
• 单词搜索：问的是“存不存在一条合法路径”。格子A在路径1里被用过了，但另一条完全不同的路径仍然可以用它——限制只作用于“当前这条路径”。所以用完必须还回去。

一句话判据：如果“访问过”这件事对整个问题永久成立 → 普通DFS；如果只对当前路径成立 → 回溯（要撤销）。这条判据是今天全篇的钥匙。

📦 题目速览 LeetCode 79（30 秒读懂）

题目1：单词搜索（LC.79）

在m × n字符网格中，判断word是否存在。单词按字母顺序、通过上下左右相邻格子构成，同一格不能重复使用。

示例：网格含ABCCED→true；ABCB→false（B不够）
约束：m,n ≤ 6，word长度 ≤ 15。

题目2：解数独（LC.37，作拓展讲）

填充空格，使每行、每列、每宫都是1-9不重复。

🧠 核心思路：四方向 + 原地标记 + 三处剪枝

3.1 骨架：三个固定动作

1. 越界判断：0 <= r < m and 0 <= c < n
2. 四方向扩展：DIRS = [(1,0), (-1,0), (0,1), (0,-1)]，写成常量数组循环调dfs
3. 就地标记：把访问过的格子改成'#'，回溯时改回来

为什么用原地标记而不是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）：

快了约47,000 倍，代价只是两个Counter（O(m·n) 预处理）。

剪枝三（必须的）：找到即层层短路

dfs返回bool，一旦某个方向返回True，立刻return True向上传递，不要继续遍历其余方向。

3.3 拓展：解数独——返回值是bool的“全填完才算解”

数独的关键优化：MRV启发式——每步优先选候选数字最少的空格。原因很直觉：候选最少的格子最容易“暴露矛盾”，早失败早回头。

实测（经典例题，51个空格）：

节点少81倍，快15.7倍——同一份骨架，只换“先填谁”的顺序。

🖼️ 图解算法（手把手走一遍）

LC.79：走出“ABCCED”

关键点：路径里C用了两次，但它们是两个不同格子——这正是“同一单元格不能重复使用”的准确含义。

递归栈与原地标记的逐帧快照

如果不还原会怎样？假设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 + Java）

Python版

fromcollectionsimportCounterclassSolution:# ============ LC.79 单词搜索 ============defexist(self,board:List[List[str]],word:str)->bool:m,n=len(board),len(board[0])# 剪枝②：字符频次预处理board_cnt=Counter(chforrowinboardforchinrow)word_cnt=Counter(word)forch,needinword_cnt.items():ifboard_cnt[ch]<need:returnFalseDIRS=((1,0),(-1,0),(0,1),(0,-1))defdfs(r,c,i):ifi==len(word):# 全部匹配完 = 成功returnTrueifnot(0<=r<mand0<=c<n):# 边界returnFalseifboard[r][c]!=word[i]:# 字符不匹配（'#' 也在这被拦）returnFalseboard[r][c]='#'# 原地标记fordr,dcinDIRS:ifdfs(r+dr,c+dc,i+1):# 找到即层层短路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):v=board[r][c]ifv=='.':blanks.append((r,c))else:rows[r].add(v);cols[c].add(v);boxes[(r//3)*3+c//3].add(v)defcandidates(r,c):b=(r//3)*3+c//3return[vforvin"123456789"ifvnotinrows[r]andvnotincols[c]andvnotinboxes[b]]defbacktrack(k):ifk==len(blanks):returnTrue# MRV：挑候选最少的空格先填best,best_cand=k,Noneforidxinrange(k,len(blanks)):r,c=blanks[idx]cand=candidates(r,c)ifbest_candisNoneorlen(cand)<len(best_cand):best,best_cand=idx,candiflen(cand)<=1:breakblanks[k],blanks[best]=blanks[best],blanks[k]r,c=blanks[k]b=(r//3)*3+c//3forvinbest_cand:board[r][c]=v rows[r].add(v);cols[c].add(v);boxes[b].add(v)ifbacktrack(k+1):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.board=board;this.m=board.length;this.n=board[0].length;this.word=word;// 剪枝②：字符频次预处理int[]cnt=newint[128];for(char[]row:board)for(charch:row)cnt[ch]++;for(charch:word.toCharArray()){if(--cnt[ch]<0)returnfalse;}for(intr=0;r<m;r++){for(intc=0;c<n;c++){if(board[r][c]==word.charAt(0)&&dfs(r,c,0))returntrue;}}returnfalse;}privatebooleandfs(intr,intc,inti){if(i==word.length())returntrue;if(r<0||r>=m||c<0||c>=n)returnfalse;if(board[r][c]!=word.charAt(i))returnfalse;board[r][c]='#';// 原地标记for(int[]d:DIRS){if(dfs(r+d[0],c+d[1],i+1))returntrue;// 找到即短路}board[r][c]=word.charAt(i);// 撤销returnfalse;}}

⚠️防坑提醒（必看）：

• 原地标记的哨兵字符要选输入中不可能出现的（用'#'很安全）。
• 撤销必须写在所有方向都失败之后。
• “找到即短路”分支里可以故意不还原——因为函数即将返回，board不再被使用。但若题目改成“找出所有路径”，就必须还原。
• 数独的boxes[(r/3)*3 + c/3]别写错成(r/3) + (c/3)。

实测数据（本机运行）

LC.79 官方三例：

频次剪枝的威力（极限压测）：

“存在”与“拼不出”的对比：

“拼不出”比“拼得出”贵15倍——因为失败要穷尽所有可能路径才能下结论。

LC.37 解数独（51个空格）：

⏱️ 复杂度分析（面试必问）

为什么是3ᴸ不是4ᴸ？4个邻居里有1个是来路，已被标记'#'，必然不匹配。说3ᴸ能体现你想过“不能回头”这件事。

一条通用经验：网格回溯的时间 =起点数 × 分支因子^深度。优化就砍这三个数中的任何一个。

🚀 举一反三：7道高频变体题

💬 面试追问模拟（提前准备，惊艳全场）

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相邻字符在棋盘上必须存在至少一对相邻格子；
④ 超长word（L > m·n）直接判否。

Q4：解数独为什么MRV快这么多？

因为回溯代价主要由失败的子树决定。候选最少的格子能把矛盾提前暴露：填错一个唯余格，立刻return false砍掉整棵子树；按行列顺序填，可能要填十几个才撞上矛盾。本质是改变搜索树形状，也是所有 CSP 求解器的标准启发式。

🧩 实战小技巧（刷题党必备）

• 口诀：网格回溯 = DFS + 一个撤销；永久标记是普通DFS，临时标记才是回溯。
• 模板：四方向 + 边界 + 原地标记 + 找到即短路 + 撤销。
• 防坑：撤销写在所有方向失败之后；频次剪枝别省。

📈 实际应用场景（不止是刷题）

• 拼字游戏：Boggle、Wordle类
• 路径规划：走迷宫、机器人寻路
• 图像处理：连通区域标记
• 约束求解：数独、排课、排班
• 芯片布线：走线冲突检测

🎁 今日思考题

LC.79的“找到即短路”分支里，还原board[r][c]是必须的吗？
提示：从“函数即将返回、board不再被使用”的角度想。

但如果这是一道要返回所有路径的题（比如 LC.212找所有单词），答案就完全不同了——想想为什么。