岛屿数量
这题本质上不是在数格子，而是在数连通块。每次找到一块没访问过的陆地，就把整块岛“淹掉”。
问题描述
LeetCode 200 - 岛屿数量
给定一个由’1’（陆地）和’0’（水）组成的二维网格，计算岛屿的数量。岛屿由水平或垂直方向相连的陆地组成，四周被水包围。
输入: grid = [
["1","1","0","0","0"],
["1","1","0","0","0"],
["0","0","1","0","0"],
["0","0","0","1","1"]
]
输出: 3
解题思路
- DFS/BFS：遍历网格，遇到’1’就进行DFS/BFS
- 标记访问：将访问过的’1’标记为’0’
- 计数：每次DFS/BFS完成，岛屿数+1
- 四个方向：上下左右四个方向扩展
为什么这样做
把网格想成图：
- 每个
'1'是一个可走节点。 - 上下左右相邻的
'1'之间连边。
那题目就在问：这个图里一共有多少个连通块。
所以只要扫到一个还没处理过的 '1'，就立刻用 DFS 或 BFS 把整块连通区域全部标记掉，然后答案加一。
Go 代码
Go 实现
func numIslands(grid [][]byte) int {
if len(grid) == 0 {
return 0
}
rows, cols := len(grid), len(grid[0])
count := 0
var dfs func(int, int)
dfs = func(r, c int) {
if r < 0 || r >= rows || c < 0 || c >= cols || grid[r][c] == '0' {
return
}
grid[r][c] = '0'
dfs(r+1, c)
dfs(r-1, c)
dfs(r, c+1)
dfs(r, c-1)
}
for r := 0; r < rows; r++ {
for c := 0; c < cols; c++ {
if grid[r][c] == '1' {
count++
dfs(r, c)
}
}
}
return count
}易错点
岛屿数量的实现很短，但经常会在“访问标记”和“方向定义”上犯错。
- 访问过的陆地一定要立刻标掉，否则会重复计数。
- 题目默认只算上下左右，不算对角线。
- 如果不想改原网格，就自己维护
visited。 - 网格 DFS 最坏可能递归很深，特别大图时可以改 BFS。
复杂度分析
| 指标 | 复杂度 | 说明 |
|---|---|---|
| 时间复杂度 | O(M×N) | 遍历所有格子 |
| 空间复杂度 | O(M×N) | 递归栈（最坏情况） |