LeetCode 200. 岛屿数量
题目描述
题意分析
网格中的字符
'1'表示陆地，'0'表示水。能沿上下左右的陆地连续走到一起的格子属于同一座岛，要返回岛屿的总数，而不是陆地格子的总数。斜对角接触不算连通，网格边界之外都视为水。一座岛的形状可以弯曲，也可以包围水域，判断依据始终是陆地之间是否存在四方向连接。下面通过把已访问陆地改成水来标记，因此会修改输入网格。
解法：BFS 原地淹没
核心思路
[!blue]
一座岛就是一整块相互连通的陆地。扫描网格时，如果遇到一块尚未处理的陆地，就说明发现了一座新岛，答案加一；但这座岛上的其他陆地都不能再单独计数，因此要立即把与它连通的整片陆地一起标记。
用广度优先搜索完成这次标记：先把起点放进队列，每次取出一个格子，再将它上下左右尚未访问的陆地加入队列。新加入的格子之后也会继续寻找自己的邻居，搜索便能沿着陆地路径不断扩展。只要某个格子与起点连通，沿途的前一个格子就会把它发现，因此不会漏掉同一座岛的任何部分。
这里直接将发现的
'1'改为'0'，表示已经访问。标记必须在入队时完成；否则一个仍在排队的格子可能被其他邻居再次发现，造成重复入队。水与已访问陆地都不再加入队列，所以每块陆地只处理一次，搜索也不会跨越水域进入另一座岛。队列清空时，当前岛屿已全部被标记。外层扫描继续寻找仍为
'1'的格子，每次重新启动搜索都对应另一座岛。因此，启动搜索的次数恰好就是岛屿数量，而不是队列取出节点的次数。
解题步骤
- 逐行扫描网格，跳过水域。
- 遇到
'1'时，岛屿数加一，将该格子改成'0'后入队。- 不断取出队首，检查其上下左右四个邻居。
- 合法且为陆地的邻居立即改成
'0'并入队。- 队列为空时，这座岛已处理完；扫描结束后返回岛屿数。
代码实现
class Solution {
private static final int[][] DIRECTIONS = {
{1, 0},
{-1, 0},
{0, 1},
{0, -1},
};
public int numIslands(char[][] grid) {
int rows = grid.length;
int cols = grid[0].length;
int islands = 0;
for (int row = 0; row < rows; row++) {
for (int col = 0; col < cols; col++) {
if (grid[row][col] != '1') {
continue;
}
// 发现尚未访问的陆地，说明找到一个新的连通块。
islands++;
ArrayDeque<int[]> queue = new ArrayDeque<>();
queue.offer(new int[] {
row,
col,
});
grid[row][col] = '0';
while (!queue.isEmpty()) {
int[] cell = queue.poll();
for (int[] direction : DIRECTIONS) {
int nextRow = cell[0] + direction[0];
int nextCol = cell[1] + direction[1];
if (nextRow < 0
|| nextRow >= rows
|| nextCol < 0
|| nextCol >= cols
|| grid[nextRow][nextCol] != '1') {
continue;
}
// 邻居入队前就标记，防止被其他格子重复加入。
grid[nextRow][nextCol] = '0';
queue.offer(new int[] {
nextRow,
nextCol,
});
}
}
}
}
return islands;
}
}
func numIslands(grid [][]byte) int {
rows, cols := len(grid), len(grid[0])
directions := [4][2]int{
{1, 0},
{-1, 0},
{0, 1},
{0, -1},
}
islands := 0
for row := 0; row < rows; row++ {
for col := 0; col < cols; col++ {
if grid[row][col] != '1' {
continue
}
// 发现尚未访问的陆地，说明找到一个新的连通块。
islands++
queue := [][2]int{
{row, col},
}
grid[row][col] = '0'
for head := 0; head < len(queue); head++ {
cell := queue[head]
for _, direction := range directions {
nextRow := cell[0] + direction[0]
nextCol := cell[1] + direction[1]
if nextRow < 0 || nextRow >= rows ||
nextCol < 0 || nextCol >= cols ||
grid[nextRow][nextCol] != '1' {
continue
}
// 邻居入队前就标记，防止被其他格子重复加入。
grid[nextRow][nextCol] = '0'
queue = append(queue, [2]int{
nextRow,
nextCol,
})
}
}
}
}
return islands
}
复杂度分析
- 时间复杂度：$O(mn)$，每个格子最多入队、出队一次。
- 空间复杂度：$O(mn)$，最坏情况下队列可容纳同阶数量的格子。
关键点总结
[!green]
- 外层扫描负责发现新岛屿，BFS 负责一次标记完整座岛。
- 入队时立即标记，保证每个陆地最多入队一次。
- 只检查上下左右四个方向，斜对角不连通。
- 代码会修改原网格；需要保留输入时应改用独立的访问数组。
易错点总结
[!yellow]
- 把字符
'1'写成整数1。- 到出队时才标记，导致同一格子重复入队。
- 加入对角方向，错误地合并两座岛。
- 访问邻居前漏掉边界检查。
- 调用后仍复用原网格，却忽略陆地已经被改成水。
相似题目
| 题目 | 难度 | 关联与区别 |
|---|---|---|
| 695. 岛屿的最大面积 | 中等 | 连通遍历相同，原题累计每块面积并取最大，本题只统计启动搜索的次数。 |
| 130. 被围绕的区域 | 中等 | 同样处理网格连通块，原题根据是否接触边界决定保留或翻转。 |
| 733. 图像渲染 | 简单 | 用洪水填充标记网格连通分量；本题统计陆地分量数，该题修改起点所属的同色分量。 |
| 1020. 飞地的数量 | 中等 | 用洪水填充标记网格连通分量；本题统计陆地分量数，该题从边界排除可逃离的陆地。 |
| 1254. 统计封闭岛屿的数目 | 中等 | 用洪水填充标记网格连通分量；本题统计陆地分量数，该题排除接触边界的零分量。 |
| 305. 岛屿数量 II | 困难 | 岛屿数量系列。II 将静态连通块计数改为逐次增加陆地，使用并查集增量合并相邻岛屿。 |
转载与许可
许可
本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！