这是一个非常核心的问题。：DFS（深度优先搜索）首先是一种思想，然后才是具体题目中的代码实现。
理解 DFS 的关键在于：“不撞南墙不回头”。
1. DFS 的本质思想
DFS 的核心逻辑是：从一个起点出发，选定一个方向死磕到底，直到走不通了（撞到边界、遇到水、或者已经访问过），再退回上一步，换个方向继续死磕。
- 二叉树中：是一路向下扎到叶子节点。
- 网格（岛屿）中：是一路向上下左右某一个方向走到底。
- 这种“回退”的动作，在代码里通过“递归”或“栈”来实现。
2. DFS 的通用“三部曲”模板
无论什么题目，DFS 的代码结构几乎都是固定的：
- 边界判定（Base Case）：我是不是出界了？我是不是已经来过这了？（防止死循环）
- 标记访问（Marking）：既然我来了，就给这里打个标记，免得一会儿又绕回来。
- 递归搜索（Recursion）：往所有可能的方向继续走。
3. 为什么《岛屿数量》的操作就是 DFS？
importsys# 设置递归深度限制，防止大矩阵导致栈溢出sys.setrecursionlimit(200000)defsolve():# 1. 处理输入 (ACM 模式常见写法)input_data=sys.stdin.read().split()ifnotinput_data:return# 获取行数和列数rows=int(input_data[0])cols=int(input_data[1])# 将剩余的一维数据填充进二维网格 grid[rows][cols]grid=[]foriinrange(rows):# 每一行取 cols 个元素start=2+i*cols grid.append(list(input_data[start:start+cols]))# 2. 定义 DFS 沉岛函数defdfs(r,c):# 边界条件：坐标越界 或 遇到水('0') 则返回ifr<0orr>=rowsorc<0orc>=colsorgrid[r][c]=='0':return# 沉岛操作：将当前陆地标记为 '0'，防止重复访问grid[r][c]='0'# 递归访问上下左右四个方向dfs(r-1,c)# 上dfs(r+1,c)# 下dfs(r,c-1)# 左dfs(r,c+1)# 右# 3. 遍历网格寻找岛屿island_count=0forrinrange(rows):forcinrange(cols):# 只要发现一块陆地，就是一个新岛屿的开始ifgrid[r][c]=='1':island_count+=1# 使用 DFS 把它连通的所有陆地全部“淹没”dfs(r,c)# 4. 输出结果print(island_count)if__name__=="__main__":solve()对比上面的模板，你看《岛屿数量》的代码逻辑：
- 起点：遍历整个网格，遇到
'1'（陆地）就开工。 - 死磕到底：
dfs(r+1, c)、dfs(r-1, c)… 这就是在往四个方向死磕。 - 撞墙回头：遇到边界或
'0'（水）就return。 - 标记：把
'1'变成'0'。
索引是从 0 开始的（0-indexed）。
在编程中，这是一个非常经典且容易出错的“差一错误”（Off-by-one error）。我们可以通过一个小例子看明白：
1. 为什么r >= rows必须拦截？
假设你的网格有3 行（即rows = 3）：
- 第 1 行的索引是
0 - 第 2 行的索引是
1 - 第 3 行的索引是
2
最大的合法索引是rows - 1（也就是 2）。
如果你此时代码里的r等于3（即r == rows），你去访问grid[3]，程序会立刻报错：IndexError: list index out of range。因为第 4 行（索引为 3 的行）根本不存在。
2. 这个条件的逻辑拆解
这一行判定条件其实是给递归设定的**“安全护栏”**：
ifr<0orr>=rowsorc<0orc>=colsorgrid[r][c]=='0':r < 0: 往“上”走过头了（出了天花板）。r >= rows: 往“下”走过头了（出了地板）。c < 0: 往“左”走过头了（出了左墙壁）。c >= cols: 往“右”走过头了（出了右墙壁）。grid[r][c] == '0': 没出界，但踩到水了，不需要处理。
只有避开了以上所有“雷区”，我们才能安全地执行grid[r][c]的操作。
3. 一个帮你记住的口诀
在处理矩阵题目时，你可以记住这个**“合法区间”**：
索引的范围是 。
只要“等于”或“超过”了长度，就是非法。
💡 进阶小技巧：为什么顺序很重要？
在这一行代码中，条件的顺序其实救了程序的命：
# 正确顺序：先判断边界，再访问数组ifr<0orr>=rowsor...orgrid[r][c]=='0':Python 在执行or时有**“短路逻辑”**：
- 如果
r >= rows成立（比如3 >= 3为真），Python 会认为整个if已经成立了。 - 它不会再去执行后面的
grid[r][c] == '0'。 - 这样就巧妙地避免了在索引越界时去访问数组导致的崩溃。
如果你把顺序反过来写：if grid[r][c] == '0' or r >= rows ...
程序会先尝试访问grid[3][c]，然后直接报错死掉，根本没机会运行到后面的边界检查。
为什么这叫 DFS？因为它会先把某一个方向相连的所有陆地全部摸透，然后再返回去摸另一条分支。这完美符合“深度优先”的定义。
4. 具体情况具体分析：不同结构的 DFS
虽然思想统一，但针对不同数据结构，DFS 的“方向”和“标记”方式不同：
A. 二叉树的 DFS
- 方向：只有两个（左孩子、右孩子）。
- 标记：通常不需要手动标记，因为树的结构是向下的，不会往回走。
- 代码：
dfs(node.left)dfs(node.right)。
B. 二维数组（网格/岛屿）的 DFS
- 方向：四个或八个（上下左右，有时加斜向）。
- 标记：必须标记（沉岛或
visited数组），因为网格是连通的，不标记会死循环。 - 代码：
dfs(r+1, c)、dfs(r, c+1)等。
C. 排列组合题的 DFS（回溯）
- 方向：数组中还没用过的数字。
- 标记：
used[i] = True递归used[i] = False（回溯的关键：撤销标记）。 - 区别：岛屿题不需要撤销标记（沉了就沉了），但排列题需要撤销（为了尝试下一种排列）。
5. 总结：DFS 的通用细节表
| 维度 | 二叉树 DFS | 网格岛屿 DFS | 全排列 DFS (回溯) |
|---|---|---|---|
| 终止条件 | if not node | if 越界 or grid[i][j]=='0' | if 路径长度 == 目标长度 |
| 访问标记 | 无需（通常） | 沉岛（将 1 改为 0） | used 数组 |
| 扩散方式 | left/right | 上下左右 | for i in range(len(nums)) |
| 是否回溯 | 否 | 否 | 是（必须恢复现场） |
💡 备考建议
你在面试中，如果听到“连通性”、“所有路径”、“寻找所有可能的组合”，脑子里第一反应就应该是DFS。
《单词搜索 (LeetCode 79)》。这题也是网格，但它比岛屿数量多了一个**“回溯”的动作（因为路走不通要退回来，把标记还原）。
这道题是DFS + 回溯 (Backtracking)的教科书级案例。它和《岛屿数量》非常像，但多了一个关键动作：“恢复现场”**。
在《岛屿数量》中，岛沉了就沉了；但在《单词搜索》中，如果你这一条路没走通，你得把踩过的脚印擦掉，给别的路径留机会。
1. 核心思路：DFS + 回溯
- 遍历网格：在 的网格里，找到第一个和单词
word[0]匹配的字母，作为 DFS 的起点。 - 深度搜索：从起点开始，向四个方向扩散，寻找
word[1],word[2]… - 标记与回溯：
- 为了防止“同一个格子重复使用”，我们在进入递归前，把当前格子标记（比如改成空字符
''）。 - 关键点：如果这条路最终没能找到完整的单词，在
return之前，必须把当前格子的字符改回来。这就是回溯。
2. 手写代码实现（LeetCode 风格）
classSolution:defexist(self,board:list[list[str]],word:str)->bool:rows=len(board)cols=len(board[0])defdfs(r,c,k):""" r, c: 当前网格坐标 k: 当前匹配到 word 的第几个字符 """# 1. 边界判定 + 字母匹配判定# 利用短路逻辑：先看坐标是否越界，再看字符是否匹配ifr<0orr>=rowsorc<0orc>=colsorboard[r][c]!=word[k]:returnFalse# 2. 成功条件：如果匹配到了单词的最后一个字母ifk==len(word)-1:returnTrue# 3. 标记访问：防止原地转圈（同一个格子重复使用）temp=board[r][c]board[r][c]=''# 临时清空# 4. 四个方向死磕：只要有一个方向通了，就返回 True# 注意：k+1 代表去找下一个字母res=(dfs(r+1,c,k+1)ordfs(r-1,c,k+1)ordfs(r,c+1,k+1)ordfs(r,c-1,k+1))# 5. 回溯：擦掉脚印，恢复现场！# 无论 res 是 True 还是 False，都要把字母还回去board[r][c]=tempreturnres# 主逻辑：寻找起点forrinrange(rows):forcinrange(cols):ifdfs(r,c,0):returnTruereturnFalse3. 这题和《岛屿数量》的细节差异
| 细节 | 岛屿数量 (Island) | 单词搜索 (Word Search) |
|---|---|---|
| 匹配目标 | 只要是 ‘1’ 就行 | 必须匹配word[k] |
| 递归深度 | 直到把整块岛淹没 | 直到k == len(word) - 1 |
| 标记处理 | 永久修改(把 1 变成 0) | 暂时修改(回溯时要改回来) |
| 返回值 | 不需要返回 (void) | 必须返回bool(通了还是没通) |
在《岛屿数量》里，我们是把陆地炸掉，炸了就炸了；但在《单词搜索》里，我们要寻找的是一条特定的路径。
1. 为什么要“标记”？ (步骤 3)
假设你要找单词ABA，而网格里是A - B两个格子。
- 你站在第一个
A上，匹配成功。 - 此时你往右走到
B，匹配成功。 - 接下来你要在
B的四周找下一个A。如果没有标记，你会回头看向左边那个刚刚才用过的A。 - 程序会觉得：“哎？左边刚好有个
A！” 于是判定ABA存在。
但这不符合题意，因为同一个格子不能重复使用。所以，我们每踩到一个格子，就要把它暂时“变成空”，让后面的递归看不见它。
2. 为什么要“回溯/恢复现场”？ (步骤 5)
这是最难理解的地方。我们用一个真实的例子来说明：
假设网格如下，你要找单词ABCE：
[A] [B] C D [E] F路径有两条可能：
- 路径 1：A -> B -> C -> … (走不通了，没找到 E)
- 路径 2：A -> B -> E (成功！)
关键点来了：
- 程序先试探路径 1。当它走到
B的时候，它会尝试往右走去摸C。 - 为了防止回头，它会把
B改成空''。 - 如果往
C走的那条路彻底失败了，程序会回退（Return）到B这个位置。 - 如果不恢复
B：当程序尝试路径 2（从A走到下面的D或者尝试其他分身）时，它发现B还是空的！原本能通过B到达E的路，因为之前失败的尝试，被永久封死了。
3. 视觉化流程：做实验
想象你是一个实验员，在一个培养皿（网格）里找路径：
- 拿起（temp = board[r][c]）：你把当前的显微镜玻片拿起来观察。
- 遮住（board[r][c] = ‘’）：在这一片放个遮光板，防止等会儿光线乱跳。
- 观察四周（res = dfs…）：看看上下左右能不能接上。
- 放下（board[r][c] = temp）：不管观察结果如何，你走的时候必须把遮光板拿走，把玻片放回原处。因为下一个实验员（另一条路径的递归）可能需要用到这片玻片。
4. 代码执行的细节顺序
temp=board[r][c]# 1. 记住这里本来是 'B'board[r][c]=''# 2. 把它涂掉，让递归里的下一层看不见它res=(dfs...)# 3. 递归像分身一样出去找，它们看到的 board[r][c] 都是空的board[r][c]=temp# 4. 分身回来了，赶紧把 'B' 涂回来returnres# 5. 带着结果向上级汇报总结
- 标记：是为了约束当前这一条路径不走回头路。
- 回溯：是为了不影响其他可能的路径。
面试官追问：“回溯的时间复杂度很高，怎么优化？”
你：“对于这道题，回溯是必须的，但我们可以做剪枝（Pruning）。比如先统计网格里各字母的数量，如果网格里A只有 1 个，而单词里需要 2 个A，直接返回False，连 DFS 都不用进。”
面试官经常会问：“如果不允许修改原数组（board），你该怎么做？”
回答：“我可以维护一个同样大小的二维布尔数组visited[m][n]，或者使用一个哈希表（Set）来记录访问过的坐标 。”
)