LeetCode-Go 题解200. Number of Islands岛屿数量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 开源仓库中的第 200 题「岛屿数量Number of Islands」为核心完整讲解题目含义、DFS 深度优先搜索解题思路、仓库内 Go 源码的逐行实现、边界条件处理与测试用例验证并顺带对比仓库内同源的第 695 题「岛屿最大面积」帮助读者掌握一类经典的「二维网格连通分量计数」问题。读完本文你将能够独立写出 100% 正确且带完整测试的 Go 版岛屿计数代码并理解它与单词搜索、洪水填充类题目的共通套路。题目原文题目要求如下Given a 2d grid map of1s (land) and0s (water), count the number of islands. An island is surrounded by water and is formed by connecting adjacent lands horizontally or vertically. You may assume all four edges of the grid are all surrounded by water.即给定一个由1陆地和0水组成的二维网格计算岛屿的数量。一个岛屿被水包围并且由水平或垂直方向上相邻的陆地连接而成。可以假设网格的四条边均被水包围。示例 1输入11110 11010 11000 00000输出1分析左上角 5 块陆地全部通过上下左右相邻关系连成一片周围被水和边界包围因此整个网格只有 1 个岛屿。示例 2输入11000 11000 00100 00011输出3分析左上角11/11四块陆地连成 1 个岛正中间00100中的1孤立成 1 个岛右下角11两块陆地水平相连成 1 个岛。三者互不相连共 3 个岛屿。题目大意给定一个由1陆地和0水组成的二维网格计算岛屿的数量。一个岛被水包围并且它是通过水平方向或垂直方向上相邻的陆地连接而成的。可以假设网格的四个边均被水包围。需要特别注意的是题目中的网格元素是字符1与0byte 类型而不是整数 1 和 0比较时必须使用grid[i][j] 1不能写成 1。解题思路要找出地图中的孤岛核心在于“标记”而非“删除”孤岛的含义是四周被海水包围的岛。因此解题分为两层遍历触发点遍历整个网格只要遇到一个值为1且尚未被访问过的格子就说明发现了一个新岛屿计数器加一连通区域扩散从这个格子出发向上下左右四个方向递归搜索所有相邻的陆地把它们全部标记为“已访问”。这样整个连通分量只被计数一次。从源码结构看这一题的实现与仓库内 第 79 题 Word Search单词搜索 的思路同源都是在地图上任意起点向 4 个方向做 DFS 搜索区别在于第 79 题搜索的目标是一条具体的单词路径而本题搜索的目标是把整块连通的陆地全部标记完毕。两题的源码都复用了同一个四方向偏移数组dir和相同的越界判断函数isInBoard。复杂度分析时间复杂度O(m × n)其中 m 为行数、n 为列数。每个格子最多被访问一次访问后即被标记DFS 的总工作量与网格大小线性相关空间复杂度O(m × n)最坏情况整张网格全是陆地下递归深度可达 m × n同时还需要一个与网格等大的visited布尔矩阵。如果追求更优空间可以借鉴后文第 695 题的做法直接把原网格中的1改写为0来省去visited数组。仓库源码实现解析仓库内本题的完整实现位于 200. Number of Islands.go代码风格遵循 Google Go 风格规范见仓库根目录 README.md 的说明。下面逐段解读。1. 四方向偏移数组var dir [][]int{ {-1, 0}, {0, 1}, {1, 0}, {0, -1}, }dir定义了从当前格子出发的四个邻接方向上、右、下、左。DFS 扩展时依次尝试这四个方向即可覆盖所有水平/垂直相邻的陆地而不包含斜对角方向这与题目的“水平或垂直相邻”定义严格一致。2. 主函数网格遍历 岛屿计数func numIslands(grid [][]byte) int { m : len(grid) if m 0 { return 0 } n : len(grid[0]) if n 0 { return 0 } res, visited : 0, make([][]bool, m) for i : 0; i m; i { visited[i] make([]bool, n) } for i : 0; i m; i { for j : 0; j n; j { if grid[i][j] 1 !visited[i][j] { searchIslands(grid, visited, i, j) res } } } return res }关键点空网格防御先判断m 0再判断n 0二者任一为零都直接返回 0。这对应测试用例中的空数组[][]byte{}和单行空数组[][]byte{{}}两种边界情况visited 矩阵visited[i][j]记录格子(i, j)是否已被某个岛屿的 DFS 访问过初始全为false计数触发条件只有当grid[i][j] 1且!visited[i][j]时才启动一次新的 DFS 并res。这正是遇到新的未访问陆地就相当于遇到新岛屿这一思路的直接体现。由于 DFS 会把整块连通陆地全部标记同一岛屿内部的其余陆地不会再触发计数。3. DFS 泛洪搜索函数func searchIslands(grid [][]byte, visited *[][]bool, x, y int) { (*visited)[x][y] true for i : 0; i 4; i { nx : x dir[i][0] ny : y dir[i][1] if isInBoard(grid, nx, ny) !(*visited)[nx][ny] grid[nx][ny] 1 { searchIslands(grid, visited, nx, ny) } } }这段是洪水填充flood fill的经典写法进入函数第一步先把当前格子(x, y)标记为已访问防止回头访问造成死循环依次检查四个方向的邻居(nx, ny)同时满足三个条件才继续递归在网格内isInBoard、未被访问!visited、是陆地 1注意visited以*[][]bool指针形式传递确保递归层与外部主循环共享同一份访问记录如果不传指针Go 的切片虽然本身是引用类型但visited的底层数组共享直接传[][]bool也能生效——这里显式传指针语义上更明确地表达修改共享状态的意图当前格子被标记后后续主循环再扫描到它时会因visited[i][j] true而跳过不会重复计数。4. 越界判断工具函数func isInBoard(board [][]byte, x, y int) bool { return x 0 x len(board) y 0 y len(board[0]) }isInBoard统一负责坐标合法性校验x必须在[0, len(board))y必须在[0, len(board[0]))。把越界判断抽成独立函数既避免在每个递归分支里重复写条件也让 DFS 主体代码更清爽。这个工具函数与 第 79 题 Word Search 中的isInBoard实现完全一致进一步印证了两题共用同一套模板。完整源码汇总将上述四部分组合起来就是仓库内 200. Number of Islands.go 的完整实现。整体流程可以概括为初始化visited全false双重循环扫描网格命中新陆地即res并递归标记整块岛返回计数结果。测试用例验证仓库为本题提供了完备的表驱动测试位于 200. Number of Islands_test.go其中para表示输入参数二维byte网格ans表示期望输出岛屿数量。type question200 struct { para200 ans200 } // para 是参数 // one 代表第一个参数 type para200 struct { one [][]byte } // ans 是答案 // one 代表第一个答案 type ans200 struct { one int }测试覆盖了四组典型输入输入网格期望输出覆盖点11110 / 11010 / 11000 / 000001题目示例 1大块连通陆地11000 / 11000 / 00100 / 000111 和 3 两组题目示例 2 及变体多个互不相连岛屿[][]byte{}0空网格无行[][]byte{{}}0只有一行的空网格无列测试主函数Test_Problem200遍历所有用例调用numIslands(p.one)并与期望值比较不一致时通过t.Fatalf立即失败同时用fmt.Printf打印输入输出便于人工核对for _, q : range qs { a, p : q.ans200, q.para200 out : numIslands(p.one) fmt.Printf(【input】:%v 【output】:%v\n, p, out) if out ! a.one { t.Fatalf(input %v expected %v got %v, p, a.one, out) } }如何运行测试仓库根目录提供了统一的测试脚本 gotest.sh它会用go test -covermodeatomic -coverprofilecoverage.txt ./leetcode/...一次性对整个leetcode包进行覆盖率收集保证所有题解包括本题达到 100% 的测试覆盖率目标。也可以只针对本题单独运行go test -v -run Test_Problem200 ./leetcode/0200.Number-of-Islands/运行前提本地已安装 Go 工具链项目为 Go module 工程仓库根目录存在 go.mod 与 go.sum。同源题对比695. Max Area of Island理解本题之后可以顺便对照仓库内同属岛屿主题的 第 695 题 岛屿最大面积。二者的区别与联系非常清晰计数 vs 求面积第 200 题每次发现新岛屿只做一次res不关心岛有多大第 695 题则要求在 DFS 过程中累计每个岛屿包含的陆地格子数并维护全局最大值标记方式不同第 695 题的实现见 695. Max Area of Island.go没有额外分配visited矩阵而是直接把访问过的陆地grid[x][y]改写为0相当于沉岛从而在节省空间的同时避免重复访问第 200 题则保持输入网格只读用独立的visited记录访问状态——两种策略各有取舍是理解原地修改 vs 额外标记这两种 flood fill 写法的绝佳案例输入类型不同第 695 题网格元素是整数int判断时用grid[i][j] 0而第 200 题是byte字符判断时用 1共用模板两题的 DFS 核心结构几乎一致——同一个dir四方向数组、同样的越界检查、同样的递归展开方式。掌握第 200 题的写法等于同时掌握了第 695 题、第 79 题单词搜索乃至一切二维网格连通性搜索题目的骨架。小结通过 LeetCode-Go 仓库中第 200 题的完整源码与测试可以总结出这类网格连通分量计数问题的四步通用模板定义四方向偏移数组dir双重循环扫描网格命中目标且未访问则计数并启动 DFSDFS 内部先标记当前格再向四个方向递归扩展用独立的越界判断函数统一处理边界。本文涉及的源码、测试与关联题目均可在仓库内直接查看第 200 题实现、第 200 题测试、第 79 题实现、第 695 题实现。【免费下载链接】LeetCode-Go✅ Solutions to LeetCode by Go, 100% test coverage, runtime beats 100% | LeetCode 题解项目地址: https://gitcode.com/GitHub_Trending/le/LeetCode-Go创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考