岛屿数量
给你一个由 ‘1’(陆地)和 ‘0’(水)组成的的二维网格,请你计算网格中岛屿的数量。
岛屿总是被水包围,并且每座岛屿只能由水平方向和/或竖直方向上相邻的陆地连接形成。
此外,你可以假设该网格的四条边均被水包围。
示例 1:
输入:grid = [
["1","1","1","1","0"],
["1","1","0","1","0"],
["1","1","0","0","0"],
["0","0","0","0","0"]
]
- 输出:1
示例 2:
输入:grid = [
["1","1","0","0","0"],
["1","1","0","0","0"],
["0","0","1","0","0"],
["0","0","0","1","1"]
]
- 输出:3
提示:
- m == grid.length
- n == grid[i].length
- 1 <= m, n <= 300
- grid[i][j] 的值为 ‘0’ 或 ‘1’
思考
计算岛屿数量的问题,可以使用深度优先搜索(DFS)或广度优先搜索(BFS)来解决。
DFS 算法流程:
- 遍历整个二维网格。
- 如果一个位置为1,则以其为起始节点开始进行深度优先搜索。
- 在 DFS 中,将其所有相邻四个方向的 1 都标记为已遍历。
- 计数岛屿数量,并将已遍历的 1 重新标记为 0。
- 继续遍历网格,如果遇到为 1 的位置,重复步骤 2~4。
BFS 算法流程:
- 遍历整个二维网格。
- 如果一个位置为 1,则把它加入一个队列,开始以其为起点进行广度优先搜索。
- 在BFS搜索中,取出队首位置,将其所有相邻四个方向的 1 都标记为已遍历,并加入队列。
- 重复步骤3,直到队列为空。
- 计数岛屿数量,并将已遍历的 1 重新标记为 0。
- 继续遍历网格,对新的 1 重复步骤 2~5。
题解
DFS
class Solution {
// 定义DFS搜索方法
void dfs(char[][] grid, int r, int c) {
int nr = grid.length;
int nc = grid[0].length;
// 边界条件检查,如果坐标越界或者是水域,直接返回
if (r < 0 || c < 0 || r >= nr || c >= nc || grid[r][c] == '0') {
return;
}
// 将当前格子标记为已访问
grid[r][c] = '0';
// 访问上、下、左、右四个相邻结点
dfs(grid, r - 1, c);
dfs(grid, r + 1, c);
dfs(grid, r, c - 1);
dfs(grid, r, c + 1);
}
public int numIslands(char[][] grid) {
// 异常输入检测
if (grid == null || grid.length == 0) {
return 0;
}
int nr = grid.length;
int nc = grid[0].length;
int num_islands = 0;
// 遍历整个网格
for (int r = 0; r < nr; ++r) {
for (int c = 0; c < nc; ++c) {
// 如果发现陆地,岛屿数量加1
// 并启动DFS将陆地都标记为已访问状态
if (grid[r][c] == '1') {
++num_islands;
dfs(grid, r, c);
}
}
}
return num_islands;
}
}
BFS
class Solution {
public int numIslands(char[][] grid) {
// 异常情况处理
if (grid == null || grid.length == 0) {
return 0;
}
int nr = grid.length;
int nc = grid[0].length;
int num_islands = 0;
for (int r = 0; r < nr; ++r) {
for (int c = 0; c < nc; ++c) {
// 如果是陆地,则增加岛屿计数
if (grid[r][c] == '1') {
++num_islands;
// 初始化一个队列,用于BFS
Queue<int[]> queue = new LinkedList<>();
queue.add(new int[] {r, c});
// 注意这里要标记已访问,避免重复计数
grid[r][c] = '0';
// BFS搜索
while (!queue.isEmpty()) {
int[] cell = queue.poll();
int row = cell[0];
int col = cell[1];
// 向四个方向扩散
if (row - 1 >= 0 && grid[row-1][col] == '1') {
queue.add(new int[] {row-1, col});
grid[row-1][col] = '0';
}
if (row + 1 < nr && grid[row+1][col] == '1') {
queue.add(new int[] {row+1, col});
grid[row+1][col] = '0';
}
if (col - 1 >= 0 && grid[row][col-1] == '1') {
queue.add(new int[] {row, col-1});
grid[row][col-1] = '0';
}
if (col + 1 < nc && grid[row][col+1] == '1') {
queue.add(new int[] {row, col+1});
grid[row][col+1] = '0';
}
}
}
}
}
return num_islands;
}
}