LeetCode-Go 题解：733. Flood Fill 洪水填充——标准 Flood Fill 算法的 DFS 实现与逐行剖析-迪斯科星球

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.go）：

package 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 (x+dir[i][0] >= 0 && x+dir[i][0] < len(image)) && (y+dir[i][1] >= 0 && y+dir[i][1] < len(image[0])) && image[x+dir[i][0]][y+dir[i][1]] == oldColor { dfs733(image, x+dir[i][0], y+dir[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++，用(x+dir[i][0], y+dir[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 (x+dir[i][0] >= 0 && x+dir[i][0] < len(image)) && (y+dir[i][1] >= 0 && y+dir[i][1] < len(image[0])) && image[x+dir[i][0]][y+dir[i][1]] == oldColor { dfs733(image, x+dir[i][0], y+dir[i][1], newColor) } } }

递归函数的执行逻辑可以拆成三步：

终止条件：image[x][y] == newColor时直接返回。注意，由于入口已保证起点颜色不等于newColor，这里的判断主要防止已经染过色的格子被重复访问，等价于一张"已访问"标记。
就地染色：记录oldColor后，把当前格image[x][y]改为newColor。这里先染色再扩散，染过色的格子自然成为递归的天然屏障，无需额外的visited二维数组，空间上非常省。
四方向扩散：对每个邻居先做双重边界检查（行、列分别判断是否越界），再判断邻居颜色是否等于oldColor，满足条件才递归深入。因为起点同色区域在递归中不断被染成newColor，所以只可能扩散到尚未染色的同色格子，整个连通区域恰好被完整覆盖。

边界安全与原地修改说明

边界判断采用x+dir[i][0] >= 0 && x+dir[i][0] < len(image)与y+dir[i][1] >= 0 && y+dir[i][1] < len(image[0])组合，确保任何递归调用都不会越界访问；
由于矩阵规模不超过50 x 50，最坏情况递归深度为 2500 层，远低于 Go 默认栈限制，可安全使用递归实现 DFS；
算法在原矩阵上直接修改，空间复杂度仅为递归栈开销。

测试用例与覆盖率：如何验证实现

仓库为本题提供了完整的表驱动测试，文件为 733. Flood Fill_test.go：

func 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场景：起点颜色为 1，newColor也为 1，验证入口函数提前返回、图像保持不变的分支。

此外，测试还直接调用了dfs733一次，用于单独覆盖递归函数中image[x][y] == newColor的提前返回守卫分支，保证这两条边界路径都被执行到。项目描述中标注了 "100% test coverage" 的目标，而仓库根目录的 gotest.sh 脚本通过go test -covermode=atomic -coverprofile=coverage.txt ./leetcode/...一次性对全部题解收集覆盖率数据，验证方式可复现：

go test -v ./leetcode/0733.Flood-Fill/ -run Test_Problem733

模块信息见仓库根目录 go.mod（module github.com/halfrost/LeetCode-Go，Go 版本 1.19）。

复杂度分析

时间复杂度：O(R x C)，其中R = len(image)、C = len(image[0])。每个像素至多被访问一次（染过色后不再递归），四方向扩散的常数开销为 4。
空间复杂度：O(R x C)，最坏情况（整个矩阵同色且newColor不同）下递归栈深度等于连通区域大小。

延伸：本仓库中同构的网格遍历家族

掌握了dir方向数组 + 先染色再扩散 + 边界检查这一套组合拳，可以无缝迁移到本仓库其他"网格连通性"类问题：

1. Number of Islands：同样是四方向 DFS，区别在于遍历整个网格寻找连通块并计数；
1. Max Area of Island：DFS 返回连通块面积，并把已访问岛屿原地置 0 防止重复统计；
1. Surrounded Regions：从边界反向 Flood Fill，标记出不被包围的区域；
1. 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），仅供参考

企业官网建设流程全解析