综述由AI生成通过多个 LeetCode 例题深入解析 Flood Fill 算法。涵盖图像渲染、岛屿数量、最大面积、被围绕区域、水流问题、扫雷及机器人运动范围等场景。重点讲解深度优先搜索（DFS）在矩阵遍历中的应用，包括边界处理、访问标记（vis）、回溯机制及正难则反的解题思路。分析了不同场景下是否需要恢复现场，以及优化剪枝策略，帮助读者掌握连通性问题的通用解法。
如果在上述矩阵的情况下，给我们的 color 不是 2，而是 1，也就是原始像素值和要修改像素值相同的情况，此时很有可能在递归的时候走重复路径：
不处理好这种特殊情况，很容易写出 bug。所以在编写代码时，先判断一下 if (image[sr][sc] == color)，直接返回即可，因为无需修改。
报错原因：没有修改 image[sr][sc] 为 color。
优化：本题并不需要 vis 数组来标记走过的格子，因为走过的格子都会修改，修改后会被剪枝条件筛查掉，并且这道题也没有递归出口，也不需要恢复现场。
为了避免走重复路径，我们定义一个 vis 数组，用来标记已经走过的小方格：
报错原因：
剪枝条件
grid[x][y] == '1'，而不是grid[x][y] == 1； ret++ 设置的位置不对，是统计完一块岛屿的时候，ret 才 +1，而上面这样设置，是在一块陆地（一个小格子）上下左右都查找完之后 +1，而不是找到一个完整的岛屿，ret 才 +1。
在下图 ret++ 设置的位置，表示以 grid[i][j] 这块陆地开始递归，向外查找别的陆地，直到找完整块联通的陆地，递归才会结束：
递归结束，表明已经找到了以 grid[i][j] 这块陆地为起点所形成的一个完整的岛屿，ret++。
恢复现场是因为决策树衍生出的多条分支，为了保证每条分支的结果，不被同层的其他已经递归过的分支影响，回溯时，就要把其他分支修改的 path 还原；
而这道题不用恢复现场，原因是因为大多数 Flood Fill 算法类型的题，是要找出一块矩阵所有的连通区，这些连通区需要被记录，因为这些连通区都会参与最终结果，且各个连通区不会出现重叠，所以在回溯时不需要也不能把记录过的连通区还原。
报错原因：count 设置为 dfs 的一个参数，无法记录整个岛屿的面积，会出现只记录一部分，回溯时把记录部分恢复的情况。
难点：如果连通的 O 区域中，只要有一块能在矩阵的边上，那么这一整块连通区 O 都不能被 X 包围，而这道题的难点就是处理这种情况。
我们对一个连通区进行深度优先遍历，直到修改完连通区所有的 O，但是如果遇到一块非法 O，我们就向上回溯，并且把修改成 X 的 O 全部恢复。
这个思路是可以的，但是代码会非常难写，因为被包围的连通区，和未被包围的连通区深度优先遍历的处理方法是不同的，按照这个思路，我们就需要写两份 dfs。
并且还有一个更致命的问题，就是我们在进行深度优先遍历时，是先搜索，才能对一块小方块的合法与否进行判断，那么在判断之前，我们并不知道应该调用哪一份 dfs。
如果直接上手写代码比较难的话，我们可以采用正难则反的方法：
处理与边界相连的区域不好上手；那么我们就可以先处理矩阵的最外围，当最外围出现 O，就把 O 所在的连通区标记一下，此时剩下的 O，就是我们应该处理的。
所以，我们可以在真正处理矩阵连通区之前，先扫描矩阵的四条边，如果四条边上扫描到 O，我们就对这个 O 进行深度优先遍历，标记遍历到的连通区，剩下的连通区就是我们要处理的。
这道题的标记方法，修改原始矩阵会比设置 vis 数组更好，因为这道题本来就是要修改原始矩阵：
本题，我们又学会了正难则反的思想，以及如何遍历矩阵的四条边。
在看这道题之前，我们先来看看题目讨论：
本文将以示例一来讲解清楚这道题要我们做什么：
我们可以暴力枚举所有的点，如果一个点可以流向大西洋和太平洋，我们就把这个点的坐标存到最终的 ret 中。
如果直接判断，代码虽然不难写，但是会判断很多重复的路径：
比如图中这个 4，如果想去太平洋，可以通过暴搜，找到所有流向中，其中能流向太平洋的一条路径：
然后我们再来枚举高度为 5 的小格子，就有可能会判断到重复的路径：
枚举小方格使用直接判断的方法，是会判断多次重复路径的，如果这个矩阵的范围非常大，那么无效的时间开销也会变得非常大。
我们最终要找的是某个点能不能流向太平洋，那我们就反过来看，我们可以假设太平洋的水逆着流，会流向哪些位置（水从海拔低的格子逆着流向海拔高或者等海拔的格子）。
为了降低时间复杂度，遍历过的格子，就不用重新遍历：
而能流向大西洋的格子同理，让大西洋的水逆向流：
此时，重复的格子就是我们最终的返回值，这些重复格子既可以流向太平洋，也可以流向大西洋：
par, atl 作为 dfs 的参数，把 par, atl 设置成全局变量也可以，设置成局部变量也可以，都能起到记录的结果不会被自动恢复作用。
算法原理就是扫雷游戏的规则，我们可以自己去玩两把感受一下。
我们以示例一来讲解扫雷游戏的步骤：
对于扫雷游戏：
本题是八联通，需要扩展向量数组：
地上有一个 m 行 n 列的方格，从坐标 [0,0] 到坐标 [m-1,n-1]。机器人从坐标 [0,0] 的格子开始移动，它每次可以向左、右、上、下移动一格（不能移动到方格外），也不能进入行坐标和列坐标的数位之和大于 k 的格子。例如，当 k 为 18 时，机器人能够进入方格 [35,37]，因为 3+5+3+7=18。但它不能进入方格 [35,38]，因为 3+5+3+8=19。请问该机器人能够到达多少个格子？
通过一次深度优先遍历，找到满足：digit(i) + digit(j) <= cnt 性质的格子即可，本题的算法原理很简单，考验的是我们的代码能力。
报错原因：不定义标记数组，ret 会统计重复走过的格子和递归回溯经过的格子的总数：
微信公众号「极客日志V2」，在微信中扫描左侧二维码关注。展示文案：极客日志V2 zeeklog
使用加密算法（如AES、TripleDES、Rabbit或RC4）加密和解密文本明文。 在线工具，加密/解密文本在线工具，online
基于开源反向 Alpha 混合算法去除 Gemini/Nano Banana 图片水印，支持批量处理与下载。 在线工具，Gemini 图片去水印在线工具，online
将字符串编码和解码为其 Base64 格式表示形式即可。 在线工具，Base64 字符串编码/解码在线工具，online
将字符串、文件或图像转换为其 Base64 表示形式。 在线工具，Base64 文件转换器在线工具，online
将 Markdown（GFM）转为 HTML 片段，浏览器内 marked 解析；与 HTML转Markdown 互为补充。 在线工具，Markdown转HTML在线工具，online
将 HTML 片段转为 GitHub Flavored Markdown，支持标题、列表、链接、代码块与表格等；浏览器内处理，可链接预填。 在线工具，HTML转Markdown在线工具，online
