LeetCode-Go 题解1034. Coloring A Border连通分量边界着色DFS 实现全解析【免费下载链接】LeetCode-Go✅ Solutions to LeetCode by Go, 100% test coverage, runtime beats 100% | LeetCode 题解项目地址: https://gitcode.com/GitHub_Trending/le/LeetCode-Go本篇技术指南以 LeetCode-Go 仓库中 1034.Coloring-A-Border 题解文档 为主体结合仓库内的 Go 源码实现 与 单元测试用例 展开。读完本文你将掌握如何用深度优先搜索DFS在网格矩阵上定位一个连通分量、判定其边界格子并完成原地染色同时理解该解法中避免“染色污染后续遍历”的关键设计。一、题目背景与问题定义LeetCode 第 1034 题“Coloring A Border”给边界着色是一道典型的网格图 连通分量问题属于图的遍历与边界判定的综合应用。题目描述如下给定一个m x n的整数矩阵grid以及三个整数row、col和color。grid中的每个值表示该位置网格块的颜色。如果两个网格块颜色相同且在四个方向上、下、左、右任意一个方向上相邻那么它们属于同一个连通分量。一个连通分量的边界由该分量内满足以下任一条件的格子组成该格子在上下左右四个方向上存在一个相邻格子不属于该连通分量该格子位于整个网格的边框上第一行、最后一行、第一列或最后一列。请使用指定颜色color为所有包含网格块grid[row][col]的连通分量的边界进行着色并返回最终的网格grid。简单来说从(row, col)出发找到与其颜色相同的整块连通区域只把这块区域的“外圈”刷成新颜色区域内部的格子颜色保持不变。这个“只改外圈、不动内部”的要求正是本题区别于普通 Flood Fill 填色的核心难点。二、边界定义的精确理解题目原文对边界的定义可以拆解为两个逻辑条件与 题解文档 中的“题目大意”一致条件一外部相邻某个属于该连通分量的格子其上下左右四个邻居中至少有一个格子的颜色与该连通分量的颜色不同即不属于该分量则该格子是边界。条件二网格边框某个属于该连通分量的格子位于grid的第一行、最后一行、第一列或最后一列上则该格子也是边界。注意两个条件都建立在“该格子属于目标连通分量”这一前提之上。一个位于网格角落的格子如果它与(row, col)不属于同一连通分量即使它位于边框上也不会被着色。这个定义在实现上的意义是判定一个格子是否为边界不能只看它自身的位置还必须知道它是否属于目标连通分量。因此正确的做法是先完整遍历出整个连通分量再逐一检查每个成员格子是否满足上述两个条件之一。三、三个示例的逐步推演原文档给出了三个覆盖典型场景的示例这里结合边界定义逐一分析。示例 1分量紧贴网格角落输入grid [[1,1],[1,2]], row 0, col 0, color 3 输出[[3,3],[3,2]]从(0,0)出发颜色为1的连通分量包含(0,0)、(0,1)、(1,0)三个格子(1,1)颜色为2不属于该分量。其中(0,0)和(1,0)位于网格边框且(1,0)的右邻居(1,1)颜色不同(0,1)的下邻居(1,1)颜色不同。因此三个格子全部是边界全部染成3得到[[3,3],[3,2]]。示例 2分量为单个格子输入grid [[1,2,2],[2,3,2]], row 0, col 1, color 3 输出[[1,3,3],[2,3,3]]从(0,1)出发颜色为2的连通分量包含(0,1)、(0,2)、(1,2)三个格子。(0,1)的上方越界、下方(1,1)颜色为3、左侧(0,0)颜色为1属于边界(0,2)位于网格边框(1,2)位于网格边框。三者均为边界染成3。该例展示了“单点邻居全部异色”与“位于网格边界”两种情形混合时的判定逻辑。示例 3全同色矩阵仅外部一圈被染色输入grid [[1,1,1],[1,1,1],[1,1,1]], row 1, col 1, color 2 输出[[2,2,2],[2,1,2],[2,2,2]]整个3x3矩阵颜色全为1从中心(1,1)出发的连通分量覆盖全部 9 个格子。此时只有最外圈的 8 个格子位于网格边框上同时它们也紧邻网格外的越界区域中心的(1,1)四个方向都是同色格子既不在边框上也不与异色格子相邻因此不是边界保持颜色1不变。最终输出外部一圈全为2中心仍为1。这个示例直观地说明了“内部格子不动”的行为——这也是本题与朴素 Flood Fill 的本质区别。四、约束条件与数据规模分析原文档列出的约束条件如下m grid.lengthn grid[i].length且1 m, n 501 grid[i][j], color 10000 row m0 col n。网格规模最多50 x 50 2500个格子颜色取值范围在1 ~ 1000。这个数据规模意味着深度优先搜索DFS递归栈的最大深度不超过 2500在 Go 默认的 goroutine 栈增长机制下完全安全同时O(m·n)的时间复杂度也绰绰有余。正因为规模小递归 DFS 成为最直观、最易读的实现选择这也是仓库题解选择 DFS 而非 BFS 的原因。五、解题思路遍历与染色分离原文档给出的解题思路只有一句话“用 bfs 进行遍历选出边界使用 color 给边界着色”。仓库实际实现选用的是DFS深度优先搜索其核心思想可以提炼为一条关键原则先完整遍历出整个连通分量并收集边界格子最后统一染色而不是在遍历过程中立刻修改格子颜色。为什么不能在 DFS 过程中直接染色因为颜色是判断“是否属于同一连通分量”的唯一依据。如果遍历到某个边界格子时立刻把它改成新颜色color后续从其他方向递归回来时这个格子的颜色已经变化会被误判为“异色邻居”或“不属于本分量”导致两种错误一是本应属于分量的内部格子被错误跳过二是边界判定被污染最终结果不可控。因此仓库实现采用了两阶段策略收集阶段从(row, col)出发 DFS只做标记用vis布尔数组记录已访问和边界判定把边界格子记录到borders切片不改动grid中的任何值染色阶段DFS 结束后统一遍历borders切片把每个边界格子的值改写为color。这种“遍历与修改解耦”的设计把复杂的图遍历逻辑与最终的颜色写入完全分离既保证了正确性也让代码意图一目了然。六、源码级实现解析仓库中的完整实现位于 1034.Coloring A Border.go核心代码与题解文档完全一致。下面逐段剖析。6.1 辅助数据结构type point struct { x int y int } type gridInfo struct { m int n int grid [][]int originalColor int }point极简的二维坐标结构体用于记录边界格子位置与四方向偏移量gridInfo把 DFS 递归中频繁访问的上下文矩阵尺寸、矩阵本体、起点颜色打包成一个结构体避免每次递归都重复传递多个参数这是对原文档代码的工程化组织从源码结构可以看出作者刻意用结构体收拢了“只读上下文”而把“会变化的访问状态”留在函数参数中传递。6.2 主函数 colorBorderfunc colorBorder(grid [][]int, row, col, color int) [][]int { m, n : len(grid), len(grid[0]) dirs : []point{{1, 0}, {-1, 0}, {0, 1}, {0, -1}} vis : make([][]bool, m) for i : range vis { vis[i] make([]bool, n) } var borders []point gInfo : gridInfo{ m: m, n: n, grid: grid, originalColor: grid[row][col], } dfs(row, col, gInfo, dirs, vis, borders) for _, p : range borders { grid[p.x][p.y] color } return grid }主函数的关键步骤方向数组dirs{{1, 0}, {-1, 0}, {0, 1}, {0, -1}}依次对应下、上、右、左四个方向用于生成当前格子的四个邻居坐标访问标记vism x n的布尔二维切片初始全为false防止 DFS 在连通分量内部无限循环尤其处理环形连通区域时必不可少原始颜色originalColor记录grid[row][col]的值它是后续所有“同色判定”的基准。由于染色被推迟到遍历结束之后遍历期间这个基准颜色始终保持正确边界收集DFS 结束后borders中保存了目标连通分量的所有边界格子统一染色遍历borders原地修改grid最后返回grid原地修改不复制新矩阵空间开销极小。6.3 递归核心 dfsfunc dfs(x, y int, gInfo gridInfo, dirs []point, vis [][]bool, borders *[]point) { vis[x][y] true isBorder : false for _, dir : range dirs { nx, ny : xdir.x, ydir.y if !(0 nx nx gInfo.m 0 ny ny gInfo.n gInfo.grid[nx][ny] gInfo.originalColor) { isBorder true } else if !vis[nx][ny] { dfs(nx, ny, gInfo, dirs, vis, borders) } } if isBorder { *borders append(*borders, point{x, y}) } }这是整个算法的灵魂其中对四个邻居的处理是一个二分支判断分支一邻居越界或异色 → 当前格子是边界。条件!(0 nx nx gInfo.m 0 ny ny gInfo.n gInfo.grid[nx][ny] gInfo.originalColor)综合了两类情况坐标越界nx、ny超出0, m)、[0, n)范围对应“位于网格边框”这一边界条件因为边框格子的外侧就是越界区域坐标在网格内但颜色不同对应“存在不属于该连通分量的邻居”这一边界条件。只要四个方向中任一方向命中这两种情况isBorder就被置为true当前格子判定为边界分支二邻居在网格内、颜色相同且未访问 → 递归深入。只有颜色相同属于同一连通分量且未被访问过的格子才会触发递归保证了 DFS 只在目标连通分量内部扩散不会跨越到异色区域。递归返回后若isBorder为真就把当前坐标(x, y)追加到borders切片通过指针*borders在递归层间共享累积结果。值得特别指出的是边界判定的时机isBorder的判定依赖“邻居是否是异色/越界”这一事实而遍历期间grid完全未被修改因此每次判定都是基于原始颜色进行的不会出现前文所述的“染色污染”问题。七、复杂度分析时间复杂度O(m·n)。每个格子最多被访问一次由vis保证每个格子只检查固定 4 个方向的邻居因此总操作次数与格子总数线性相关空间复杂度O(m·n)。主要由三部分构成vis布尔矩阵占m·n递归栈在最坏情况下连通分量覆盖整个网格深度为m·nborders切片最多存储m·n个边界格子。八、测试用例验证仓库为本题编写了完整的单元测试位于 [1034.Coloring A Border_test.go。测试采用本仓库统一的question para ans组织模式para1034封装输入参数grid、row、col、colorans1034封装期望输出ansTest_Problem1034将前文三个官方示例作为测试用例逐一执行并用colorBorder的实际输出与期望答案对比。测试结构从源码可以清晰看出仓库的工程约定每个题解目录都包含“题解文档 实现文件 测试文件”三位一体的结构。整个仓库通过 gotest.sh 脚本统一执行go test -covermodeatomic -coverprofilecoverage.txt ./leetcode/...以原子覆盖率模式对leetcode包下的全部题目进行回归验证保证每个题解都被测试用例覆盖。如果你在本地克隆了本仓库可以按如下方式单独运行本题的测试cd leetcode go test -run Test_Problem1034 -v或在仓库根目录运行全量测试脚本bash gotest.sh九、扩展思考从 DFS 到 BFS 与同类题型原文档解题思路提到“用 bfs 进行遍历”仓库实现选择了 DFS二者在本题上是完全等价的只要把递归调用改为队列辅助的层序扩散并把边界判定逻辑原样保留即可得到 BFS 版本。选择 DFS 的理由主要是实现简洁、递归逻辑与“探索四邻”的直觉完全一致。本题的“先收集、后染色”模式在算法学习中具有泛化价值与Flood Fill填充类题目的区别在于Flood Fill 通常要求把整个连通区域全部改色而本题只改边界因此必须区分“成员”与“边界成员”两种概念与岛屿类题目如 200. Number of Islands类似都需要借助vis标记或原地改值防止重复访问边界判定的技巧越界即边界同样适用于统计岛屿周长一类问题只不过本题多了一层“连通分量内部异色邻居也算边界”的规则。十、总结LeetCode 1034 题考察的核心能力是在网格图中对连通分量做受控遍历并依据“越界”与“异色邻居”两个条件精确剥离出边界。LeetCode-Go 仓库的实现通过推迟染色 独立收集边界的设计优雅地避开了遍历过程中修改颜色带来的状态污染整体代码结构清晰、边界条件完备可直接作为同类网格遍历题目的参考模板。相关文件速览题解文档题目描述、示例与解题思路Go 实现colorBorder主函数与dfs递归实现单元测试三个官方示例的回归验证gotest.sh仓库统一的覆盖率测试入口。【免费下载链接】LeetCode-Go✅ Solutions to LeetCode by Go, 100% test coverage, runtime beats 100% | LeetCode 题解项目地址: https://gitcode.com/GitHub_Trending/le/LeetCode-Go创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考