200. 岛屿数量
3 min
题目
解法：DFS
思路
核心思想是使用深度优先搜索(DFS)洪水填充算法，遍历网格并标记访问过的陆地。
该方法正确是因为每个岛屿是一个四连通分量。当从某块未访问的陆地出发进行DFS时，会递归访问并标记该岛屿所有相连的陆地，确保整个连通分量仅被计数一次。由于外层循环遍历所有单元格，且已访问的陆地会被标记为’0’，因此每个岛屿恰好被计数一次，不会遗漏或重复。
- Step 1: 遍历网格中的每个单元格
- Step 2: 当发现值为’1’的单元格时，岛屿计数加1
- Step 3: 从该单元格开始DFS，将所有相连的’1’标记为’0’
- Step 4: DFS递归访问上下左右四个方向，边界检查防止越界
复杂度
- 时间复杂度: ，其中m和n分别是网格的行数和列数。每个单元格最多被访问一次。
- 空间复杂度: ，最坏情况下递归调用栈的深度达到网格大小（整个网格都是陆地）。
代码
class Solution {
public:
int numIslands(vector<vector<char>>& grid) {
int m = grid.size();
int n = grid[0].size();
int ans = 0;
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
if (grid[i][j] == '1') {
ans++;
dfs(grid, i, j);
}
}
}
return ans;
}
void dfs(vector<vector<char>>& grid, int i, int j) {
int m = grid.size();
int n = grid[0].size();
if (i < 0 || i >= m || j < 0 || j >= n || grid[i][j] == '0') {
return;
class Solution {
public:
int numIslands(vector<vector<char>>& grid) {
int m = grid.size();
int n = grid[0].size();
int ans = 0;
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
if (grid[i][j] == '1') {
ans++;
dfs(grid, i, j);
}
}
}
return ans;
}
void dfs(vector<vector<char>>& grid, int i, int j) {
int m = grid.size();
int n = grid[0].size();
if (i < 0 || i >= m || j < 0 || j >= n || grid[i][j] == '0') {
return;
}
grid[i][j] = '0'; // 标记为已访问
dfs(grid, i + 1, j);
dfs(grid, i - 1, j);
dfs(grid, i, j + 1);
dfs(grid, i, j - 1);
}
};