- 首先检查网格是否为空，如果为空，直接返回 0。
- 遍历网格中的每一个元素，当遇到陆地（
'1'）时，计数器加 1，并且通过 DFS 将与该陆地相连的所有部分标记为已访问（即设为'0'）。 - DFS 遍历过程中会检查网格的边界条件，如果越界或遇到水（
'0'），直接返回。 - 通过递归调用，处理当前陆地的上下左右四个方向的相邻部分。
复杂度分析：
- 时间复杂度：O(M * N)，其中 M 和 N 分别是网格的行数和列数。每个元素最多会被访问一次。
- 空间复杂度：O(M * N)，递归调用的栈空间最坏情况下可能需要达到整个网格的大小。
class Solution {
public int numIslands(char[][] grid) {
//处理边界
if(grid == null || grid.length == 0) {
return 0;
}
int num_Islands = 0;
//获取行,列
int rows = grid.length;
int cols = grid[0].length;
for(int i = 0; i < rows; ++i) {
for(int j = 0; j < cols; ++j) {
if(grid[i][j] == '1') {
num_Islands++;
}
// grid[i][j] = '0'; 不能在这里更新标记格子
dfs(grid, i, j);
}
}
return num_Islands;
}
private void dfs(char[][] grid, int i, int j) {
//首先提供递归出口
if(i < 0 || i >= grid.length || j < 0 || j >= grid[0].length || grid[i][j] == '0') {
return;
}
grid[i][j] = '0'; // 统一在dfs里置'0'标记格子,
dfs(grid, i - 1, j);
dfs(grid, i + 1, j);
dfs(grid, i, j - 1);
dfs(grid, i, j + 1);
}
}
该算法 2 个注意点
这个算法有两个核心注意点，必须严格遵守才能保证算法的正确性：
1. 在 dfs() 中统一标记格子，而不能在进入 dfs() 之前标记格子：
- 原因：标记格子（即将当前格子从
'1'变为'0'，表示它已被访问）是为了避免重复访问和无休止的递归。如果在进入dfs()之前就标记为'0'，那么在dfs()内，递归扩展时会发现该格子已经是'0'，导致相邻的陆地没有被正确处理，最终导致算法计算的岛屿数量错误。 - 做法：应在
dfs()内部执行标记操作，这样可以确保递归时只标记尚未访问的格子，并在遍历整个岛屿时正确处理相邻陆地。
private void dfs(char[][] grid, int i, int j) {
grid[i][j] = '0'; // 统一在进入递归时标记为已访问
// 继续向四个方向扩展
}
2. 需要根据递归出口来设计 if 判断条件，而不是在满足可以更新标记格子时作为 if 判断条件：
-
递归出口的核心作用：递归必须有明确的终止条件，否则会陷入无限递归，导致栈溢出或程序崩溃。在这道题中，递归出口应该是非法或无效的格子（如越界或水域
'0'），这样我们可以在递归扩展时及时返回，防止无效递归。 -
错误的做法：如果根据“满足可以更新格子”的条件来设计
if，你会导致没有明确的递归出口。递归将会继续向无效的格子（越界或水域）扩展，而没有办法终止。 -
正确的做法：递归出口条件应该是“不满足继续递归”的条件，比如：越界或当前格子是水（
'0'）。一旦遇到这些情况，立刻终止递归，并返回。这确保了递归只在有效的陆地格子上进行。
// 如果越界或遇到水域（'0'），直接返回，作为递归出口
if (i < 0 || i >= rows || j < 0 || j >= cols || grid[i][j] == '0') {
return;
}
综上所述：
- 统一标记：必须在
dfs()函数内部统一进行标记操作，而不能在调用dfs()之前。 - 递归出口：
if判断条件应该根据递归出口设计（即当遇到无效格子时终止），而不是根据满足更新格子来设计。递归只有在非法或无效情况下才会终止，确保算法正常工作。
这样，整个算法能够正确地处理网格中的岛屿，计算岛屿的数量不会出现错误或陷入无限递归。
