LeetCode 130. Surrounded Regions 题解并查集与 DFS 双解法剖析LeetCode-Go【免费下载链接】LeetCode-Go✅ Solutions to LeetCode by Go, 100% test coverage, runtime beats 100% | LeetCode 题解项目地址: https://gitcode.com/GitHub_Trending/le/LeetCode-Go本文围绕 LeetCode 第 130 题「Surrounded Regions被围绕的区域」展开以 leetcode/0130.Surrounded-Regions/README.md 为骨架结合 LeetCode-Go 仓库中的真实 Go 实现 130. Surrounded Regions.go 与测试用例 130. Surrounded Regions_test.go逐一讲解题目规则、边界判定、并查集与 DFS 两种解法的完整思路、源码级实现细节与复杂度。读完本文你将能够独立推导并实现「从边界反推连通性」这一经典网格类问题并掌握并查集在二维网格上的编号映射技巧。题目回顾捕获被 X 围绕的 O 区域给定一个二维棋盘board其中包含X和O字母 O。题目要求捕获所有被X围绕的区域即把这些被围绕区域里所有的O翻转flip为X。示例X X X X X O O X X X O X X O X X运行函数后棋盘变为X X X X X X X X X X X X X O X X规则要点题目原文的 Explanation被围绕的区域不会存在于边界上任何位于棋盘边界上的O都不会被填充为X任何不在边界上、或不与边界上的O相连的O最终都会被填充为X两个元素在水平或垂直方向相邻则称它们是相连的四连通不含对角线。示例中(3, 1)位置第 4 行第 2 列的O之所以保留正是因为它在棋盘边界上。而(1, 1)、(1, 2)、(2, 2)三个内部的O既不位于边界也没有任何一条四连通的路径通向边界因此全部被翻转为X。题目核心可以一句话概括与边界连通的O全部保留其余O全部变成X。题目大意中文简述给定一个包含X与O的二维矩阵找到所有被X围绕的区域并将这些区域中所有的O用X填充。被围绕的区域不会存在于边界上边界上的O不会被填充不在边界上、或不与边界上的O相连的O才会被填充。水平或垂直方向相邻即视为相连。解题思路总览正向包围难反向连通易直接思考哪些O被X围绕比较困难因为被围绕是一个全局性判断需要知道一个O的连通块是否完全被X包围。而题目给出了一个关键的等价条件一个O区域只有在与边界连通时才不会被填充。因此只需反向思考——先找出所有与边界连通的O剩下的O就是被围绕的区域。README.md 的「解题思路」小节明确给出了两类解法仓库代码 130. Surrounded Regions.go 中两种解法均有完整实现解法一并查集Union-Find——把所有边界上的O与一个特殊的哨兵节点做union()再对棋盘内部的O与其上下左右的O邻居做union()。最后凡是与哨兵节点不在同一个集合的节点都标记为X。解法二DFS / BFS——先把边界上的O标记成另一个临时字符仓库实现中使用*并递归标记所有与它们连通的O遍历结束后剩下的O全部标记为X临时字符*再还原为O。两种解法的共同前提是必须先站在边界的O出发做连通性分析再回头处理内部节点。解法一并查集Union-Find源码剖析核心思想并查集天然适合判断两个元素是否连通的问题。本题的做法是为棋盘额外创建一个哨兵节点其编号为n*m即棋盘节点总数代表虚拟边界集合遍历棋盘若节点位于边缘且是O则把它与哨兵节点union()到同一个集合若节点是内部的O则把它与上下左右四个方向中同为O的邻居union()再次遍历棋盘凡是Find(i)的结果与Find(n*m)不同的节点说明它不与边界连通将其改为X。网格到一维编号的映射实现中一个关键细节是二维坐标到一维编号的换算。设棋盘有n行、m列节点(i, j)对应编号i*m j而哨兵节点对应编号n*mm, n : len(board[0]), len(board) uf : template.UnionFind{} uf.Init(n*m 1) // 特意多一个特殊点用来标记源码注释特意多一个特殊点用来标记130. Surrounded Regions.go点明了哨兵节点的作用它不占用任何棋盘坐标仅作为一个虚拟的边界集合锚点让所有边界O归属同一个集合从而可以统一用uf.Find(n*m)判定是否与边界连通。边界合并与内部合并第一轮遍历中判断边界与内部用的是(i 0 || i n-1 || j 0 || j m-1)这个条件for i : 0; i n; i { for j : 0; j m; j { if (i 0 || i n-1 || j 0 || j m-1) board[i][j] O { // 棋盘边缘上的 O 点 uf.Union(i*mj, n*m) } else if board[i][j] O { // 棋盘非边缘上的内部的 O 点 if board[i-1][j] O { uf.Union(i*mj, (i-1)*mj) } if board[i1][j] O { uf.Union(i*mj, (i1)*mj) } if board[i][j-1] O { uf.Union(i*mj, i*mj-1) } if board[i][j1] O { uf.Union(i*mj, i*mj1) } } } }这里有一个值得注意的实现特点合并内部O时直接检查四个方向的邻居坐标而不做越界判断。这是安全的因为能进入else if分支的节点必然满足非边缘条件即i严格在0与n-1之间、j严格在0与m-1之间所以i-1、i1、j-1、j1全部在合法范围内。这种写法在保证正确性的同时省去了越界判断的开销。第二遍扫描非边界连通集合全部翻转for i : 0; i n; i { for j : 0; j m; j { if uf.Find(i*mj) ! uf.Find(n*m) { board[i][j] X } } }Find会做路径压缩因此在第二遍扫描时每个节点都能以近乎 O(1) 的开销找到所在集合的代表元素。凡是与哨兵不在同一集合的节点都会被改写为X边界及其连通区域保持O不变。底层数据结构template.UnionFind本题解复用了仓库模板库中的通用并查集实现 template/UnionFind.go。该实现采用**路径压缩path compression 按秩合并union by rank**优化type UnionFind struct { parent, rank []int count int }Init(n int)初始化n个节点parent[i] irank全为 0Find(p int)先向上找到根再做一次路径压缩把路径上的所有节点直接指向根从而摊平后续查找Union(p, q int)通过Find得到两个根若相同直接返回否则将秩较小的树挂到秩较大的树上两树秩相同时目标树秩加一并让count减一TotalCount() int返回当前连通分量的个数。按秩合并保证了树高可控配合路径压缩后Find/Union的均摊时间复杂度近似为反阿克曼函数级别可以视为常数级。这也是并查集解法在本题大规模棋盘上依然高效的原因。解法二DFS 边界染色法源码剖析核心思想DFS 解法的思路更直观一共分三步对应 130. Surrounded Regions.go 中的solve1第一遍遍历只关注边界上的O以它为起点调用 DFS把所有与边界连通的O临时标记为*第二遍遍历把所有*还原为O它们是应该保留的把所有仍为O的节点翻转为X它们是真正被围绕的区域。func solve1(board [][]byte) { for i : range board { for j : range board[i] { if i 0 || i len(board)-1 || j 0 || j len(board[i])-1 { if board[i][j] O { dfs130(i, j, board) } } } } for i : range board { for j : range board[i] { if board[i][j] * { board[i][j] O } else if board[i][j] O { board[i][j] X } } } }选择临时字符*而非直接标记为O/X的原因是*既不会被误判为需要翻转的O也区别于已翻转的X避免了在递归过程中对同一连通区域反复处理或产生歧义。DFS 递归函数与四方向遍历var dir [][]int{ {-1, 0}, {0, 1}, {1, 0}, {0, -1}, } func dfs130(i, j int, board [][]byte) { if i 0 || i len(board)-1 || j 0 || j len(board[i])-1 { return } if board[i][j] O { board[i][j] * for k : 0; k 4; k { dfs130(idir[k][0], jdir[k][1], board) } } }实现要点方向数组dir依次表示上、右、下、左四个方向{-1,0}、{0,1}、{1,0}、{0,-1}与题目的水平或垂直方向相邻要求一致不包含对角线递归入口先做越界检查越界直接返回只有当当前节点是O时才染色并继续递归因此已经染色的*和本就不相关的X都会被跳过——染色即等价于 visited 标记无需额外的访问数组避免了无限递归。一个潜在的小细节是j 0 || j len(board[i])-1中使用了board[i]的长度而i已在上一条件中被确认不越界因此这里访问board[i]是安全的。BFS 变体说明同样的思路完全可以改写为 BFS用队列从边界O出发做层序扩展把与边界连通的O标记为*其余流程与 DFS 版本完全一致。DFS 与 BFS 都能保证每个节点至多被访问一次差别只在于遍历顺序正确性与复杂度相同。实际竞赛中选用哪种取决于个人习惯与栈深限制若棋盘极大可优先考虑 BFS 以避免递归栈溢出。复杂度分析设棋盘大小为n × m行数为n列数为m。并查集解法时间复杂度O(n·m·α(n·m))其中 α 为反阿克曼函数实际近似 O(n·m)。两次完整遍历各自线性扫描全部节点每次Union/Find均摊近似常数。空间复杂度O(n·m)用于存放parent与rank两个长度n*m1的数组。DFS/BFS 解法时间复杂度O(n·m)。每个节点在 DFS/BFS 过程中至多被访问常数次两次线性扫描再叠加一次 O(n·m)。空间复杂度最坏情况下递归栈深度或队列长度可达 O(n·m)不额外申请与棋盘等大的数组。两种解法在渐进复杂度上等价实际差异主要体现在常数与实现风格上。测试验证双解法互证与标准用例仓库为本题提供了完整的测试用例 130. Surrounded Regions_test.go覆盖了三个典型场景空棋盘[][]byte{}输入输出均为空验证了对空矩阵的健壮性题目标准示例4×4 棋盘期望结果中除(3, 1)边界O保留外其余全部变为X全O棋盘3×3 全O矩阵由于所有O都与边界连通最终保持全O不变——这是边界判定最容易出错的反例。测试函数的核心逻辑值得注意先用clone130深度拷贝输入分别跑solve1DFS和solve并查集再用reflect.DeepEqual断言两种解法的输出完全一致t.Fatalf(solve and solve1 differ: ...)——这是双解法互证的典型写法随后将并查集解法输出与标准答案比对若不匹配则t.Fatalf(got %v, want %v, b2, a.one)。b1 : clone130(p.one) solve1(b1) b2 : clone130(p.one) solve(b2) if !reflect.DeepEqual(b1, b2) { t.Fatalf(solve and solve1 differ: solve1%v solve%v, b1, b2) } if len(a.one) ! 0 !reflect.DeepEqual(b2, a.one) { t.Fatalf(got %v, want %v, b2, a.one) }这种两种解法互相校验 标准答案校验的测试模式在 LeetCode-Go 仓库中是对一题多解的标准验证方式可以有效防止某一种实现出现隐蔽的边界错误。全O用例的存在尤其重要它验证了边界上的O全部保留这一规则在极端输入下依然成立。易错点与实战提示必须先处理边界再处理内部无论并查集还是 DFS第一遍扫描的出发点都必须是边界O。若先处理内部节点很容易把本应与边界连通的O误判为被围绕区域。不要忽略空棋盘并查集解法在len(board) 0时直接返回DFS 解法依赖len(board)-1等下标空棋盘同样需要前置判断。O是字母 O 而非数字 0题目的字符是O大写字母 O实现与测试中不要与0混淆。内部节点合并邻居时可省去越界判断并查集解法只要当前节点确定在内部四个邻居必然合法这是仓库实现中一个干净利落的优化点。临时染色字符的选择DFS 解法用*作为中间状态保证第二遍扫描时能够区分应保留的O与应翻转的O。小结LeetCode 130 是一道非常经典的从边界反向连通类网格问题其套路先标记边界连通区域再翻转剩余部分可推广到岛屿数量、被围绕区域等一系列基于网格连通性的题目。LeetCode-Go 仓库在本目录下提供了并查集与 DFS 两种完整的 Go 实现130. Surrounded Regions.go其中并查集版本复用模板库 template/UnionFind.go 的路径压缩 按秩合并实现DFS 版本则通过方向数组与原地染色完成遍历二者由测试用例 130. Surrounded Regions_test.go 交叉验证均保证 100% 的正确性覆盖。理解两种解法的共性与差异后你可以根据实际场景灵活选用并将这套思路迁移到更多网格遍历问题中。【免费下载链接】LeetCode-Go✅ Solutions to LeetCode by Go, 100% test coverage, runtime beats 100% | LeetCode 题解项目地址: https://gitcode.com/GitHub_Trending/le/LeetCode-Go创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考