LeetCode-Go 题解733. Flood Fill 洪水填充——标准 Flood Fill 算法的 DFS 实现与逐行剖析【免费下载链接】LeetCode-Go✅ Solutions to LeetCode by Go, 100% test coverage, runtime beats 100% | LeetCode 题解项目地址: https://gitcode.com/GitHub_Trending/le/LeetCode-Go导读本文以 LeetCode 第 733 题《Flood Fill》图像渲染 / 洪水填充为核心完整继承并深化 leetcode/0733.Flood-Fill/README.md 的题目与思路同时结合仓库中 733. Flood Fill.go 的真实实现与 733. Flood Fill_test.go 的测试用例逐行展开。读完本文你将掌握 Flood Fill洪水填充算法的核心思想、在二维矩阵上使用 DFS 深度优先搜索进行四方向连通填充的 Go 实现套路以及如何借助方向数组dir与边界检查写出简洁且边界安全的递归代码。题目图像渲染Flood Fill题目描述一幅image由一个二维整数数组表示其中每个整数代表图像的像素值取值范围为 0 到 65535。给定一个坐标(sr, sc)作为洪水填充的起点像素行、列以及一个新的像素值newColor要求对图像执行一次洪水填充考虑起点像素再加上与起点像素四方向相连上下左右且颜色与起点像素相同的像素再加上与上述像素四方向相连、且颜色与起点像素相同的像素以此类推不断扩散。最终把所有被记录到的像素颜色全部替换为newColor并返回修改后的图像。输入输出示例Input: image [[1,1,1],[1,1,0],[1,0,1]] sr 1, sc 1, newColor 2 Output: [[2,2,2],[2,2,0],[2,0,1]]解释从图像中心(sr, sc) (1, 1)出发所有通过与起点同色路径相连的像素都被染成新颜色。注意右下角[2][2] 1未被染成 2因为它与起点并不四方向连通起点同色区域被值为 0 的像素隔断。数据约束image和image[0]的长度在范围[1, 50]内起点坐标满足0 sr image.length且0 sc image[0].length起点必然合法无需额外判空image[i][j]与newColor的颜色值均在[0, 65535]范围内。题目大意有一幅以二维整数数组表示的图画每一个整数表示该图画的像素值大小0 到 65535。给定坐标(sr, sc)表示图像渲染开始的像素行、列和新的颜色值newColor重新上色这幅图像从初始坐标开始记录初始坐标上下左右四个方向上像素值与初始坐标相同的相连像素点接着再记录这些像素点各自上下左右方向上像素值与初始坐标相同的相连像素点……重复该过程。最终把所有有记录的像素点颜色改为newColor返回渲染后的图像。解题思路标准的 Flood Fill 算法这是一道非常典型的Flood Fill洪水填充问题等价于在二维网格中寻找与起点同色的连通区域并把整个连通区域整体重染成新颜色。Flood Fill 是计算机图形学中经典的区域填充算法如画图工具中的油漆桶也是图遍历思想在网格上的直接应用。Flood Fill 在实现上通常有两种策略DFS深度优先搜索从起点出发沿一个方向一路走到黑遇到边界或异色像素再回溯。实现简洁栈由系统递归调用提供本题矩阵规模最大50 x 50递归深度完全可控。BFS广度优先搜索借助队列逐层向外扩散一圈一圈地染色适用于需要按距离分层处理的场景。仓库中 733. Flood Fill.go 采用 DFS 实现此外同一仓库的 1091.Shortest-Path-in-a-Binary-Matrix 等题则展示了 BFS 在网格上的应用两者可互为参照。源码级剖析仓库中的 DFS 实现仓库中floodFill的完整实现如下文件733. Flood Fill.gopackage leetcode var dir [][]int{ {-1, 0}, {0, 1}, {1, 0}, {0, -1}, } func floodFill(image [][]int, sr int, sc int, newColor int) [][]int { color : image[sr][sc] if newColor color { return image } dfs733(image, sr, sc, newColor) return image } func dfs733(image [][]int, x, y int, newColor int) { if image[x][y] newColor { return } oldColor : image[x][y] image[x][y] newColor for i : 0; i 4; i { if (xdir[i][0] 0 xdir[i][0] len(image)) (ydir[i][1] 0 ydir[i][1] len(image[0])) image[xdir[i][0]][ydir[i][1]] oldColor { dfs733(image, xdir[i][0], ydir[i][1], newColor) } } }方向数组dir四方向遍历的统一套路var dir [][]int{ {-1, 0}, // 上 {0, 1}, // 右 {1, 0}, // 下 {0, -1}, // 左 }dir是一个 4 x 2 的方向偏移表依次代表上、右、下、左四个方向。遍历邻格时只需做一次for i : 0; i 4; i用(xdir[i][0], ydir[i][1])即可枚举全部四方向邻居避免手写四段重复代码。这是整个仓库网格类 DFS 问题的通用模式——同样的dir定义也出现在 200. Number of Islands、695. Max Area of Island、130. Surrounded Regions 等题中可以推断这是本仓库解决网格连通性类问题的标准写法。入口函数newColor color的提前返回func floodFill(image [][]int, sr int, sc int, newColor int) [][]int { color : image[sr][sc] if newColor color { return image } dfs733(image, sr, sc, newColor) return image }入口函数做了两件事取出起点颜色color关键优化若newColor color即新颜色与起点颜色相同直接返回原图像不做任何递归。这一步既避免了无意义的遍历也天然防止了染色后颜色等于目标色导致递归无法终止的隐患。由于函数原地修改image因此直接return image即可符合题目返回修改后的图像的要求。递归核心dfs733染旧色、扩散新色func dfs733(image [][]int, x, y int, newColor int) { if image[x][y] newColor { return } oldColor : image[x][y] image[x][y] newColor for i : 0; i 4; i { if (xdir[i][0] 0 xdir[i][0] len(image)) (ydir[i][1] 0 ydir[i][1] len(image[0])) image[xdir[i][0]][ydir[i][1]] oldColor { dfs733(image, xdir[i][0], ydir[i][1], newColor) } } }递归函数的执行逻辑可以拆成三步终止条件image[x][y] newColor时直接返回。注意由于入口已保证起点颜色不等于newColor这里的判断主要防止已经染过色的格子被重复访问等价于一张已访问标记。就地染色记录oldColor后把当前格image[x][y]改为newColor。这里先染色再扩散染过色的格子自然成为递归的天然屏障无需额外的visited二维数组空间上非常省。四方向扩散对每个邻居先做双重边界检查行、列分别判断是否越界再判断邻居颜色是否等于oldColor满足条件才递归深入。因为起点同色区域在递归中不断被染成newColor所以只可能扩散到尚未染色的同色格子整个连通区域恰好被完整覆盖。边界安全与原地修改说明边界判断采用xdir[i][0] 0 xdir[i][0] len(image)与ydir[i][1] 0 ydir[i][1] len(image[0])组合确保任何递归调用都不会越界访问由于矩阵规模不超过50 x 50最坏情况递归深度为 2500 层远低于 Go 默认栈限制可安全使用递归实现 DFS算法在原矩阵上直接修改空间复杂度仅为递归栈开销。测试用例与覆盖率如何验证实现仓库为本题提供了完整的表驱动测试文件为 733. Flood Fill_test.gofunc Test_Problem733(t *testing.T) { qs : []question733{ // 官方示例 { para733{[][]int{ {1, 1, 1}, {1, 1, 0}, {1, 0, 1}, }, 1, 1, 2}, ans733{[][]int{ {2, 2, 2}, {2, 2, 0}, {2, 0, 1}, }}, }, // newColor color, floodFill returns image unchanged { para733{[][]int{ {0, 0, 0}, {0, 1, 1}, }, 1, 1, 1}, ans733{[][]int{ {0, 0, 0}, {0, 1, 1}, }}, }, } // ... for _, q : range qs { a, p : q.ans733, q.para733 got : floodFill(p.one, p.sr, p.sc, p.c) if !equal733(got, a.one) { t.Fatalf(floodFill(%v, %d, %d, %d) %v, want %v, p.one, p.sr, p.sc, p.c, got, a.one) } } // ... }测试覆盖了两类场景官方示例验证从中心(1,1)出发把左上2x2同色区域染成 2同时验证右下角因不连通而不被染色newColor color场景起点颜色为 1newColor也为 1验证入口函数提前返回、图像保持不变的分支。此外测试还直接调用了dfs733一次用于单独覆盖递归函数中image[x][y] newColor的提前返回守卫分支保证这两条边界路径都被执行到。项目描述中标注了 100% test coverage 的目标而仓库根目录的 gotest.sh 脚本通过go test -covermodeatomic -coverprofilecoverage.txt ./leetcode/...一次性对全部题解收集覆盖率数据验证方式可复现go test -v ./leetcode/0733.Flood-Fill/ -run Test_Problem733模块信息见仓库根目录 go.modmodule github.com/halfrost/LeetCode-GoGo 版本 1.19。复杂度分析时间复杂度O(R x C)其中R len(image)、C len(image[0])。每个像素至多被访问一次染过色后不再递归四方向扩散的常数开销为 4。空间复杂度O(R x C)最坏情况整个矩阵同色且newColor不同下递归栈深度等于连通区域大小。延伸本仓库中同构的网格遍历家族掌握了dir方向数组 先染色再扩散 边界检查这一套组合拳可以无缝迁移到本仓库其他网格连通性类问题Number of Islands同样是四方向 DFS区别在于遍历整个网格寻找连通块并计数Max Area of IslandDFS 返回连通块面积并把已访问岛屿原地置 0 防止重复统计Surrounded Regions从边界反向 Flood Fill标记出不被包围的区域Number of Enclaves边界 BFS/DFS 后统计剩余封闭区域。从这些文件可以看到var dir [][]int{...}这一方向数组模式在本仓库中被反复复用属于可以背下来的固定模板。掌握 733 题就等于掌握了这套模板的最小可运行示例。小结Flood Fill 是理解 Flood Fill 算法与网格 DFS 的最佳入门题核心思路从起点出发沿四方向扩散把与起点同色的整个连通区域染成新颜色仓库实现要点newColor color提前返回避免无效递归先染色后扩散省去visited数组dir方向数组统一四方向遍历行列双重边界检查保证安全验证方式表驱动测试覆盖官方示例与同色提前返回两条路径配合go test -coverprofile实现覆盖率统计。掌握此题之后面对任何连通区域填充 / 计数 / 周长类问题都可以直接套用本文剖析的 DFS 模板快速求解。【免费下载链接】LeetCode-Go✅ Solutions to LeetCode by Go, 100% test coverage, runtime beats 100% | LeetCode 题解项目地址: https://gitcode.com/GitHub_Trending/le/LeetCode-Go创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考