【算法面试必刷】200. 岛屿数量

目录

题目

题目链接

思路

复杂度

代码

题目

给你一个由 '1'（陆地）和 '0'（水）组成的的二维网格，请你计算网格中岛屿的数量。

岛屿总是被水包围，并且每座岛屿只能由水平方向和/或竖直方向上相邻的陆地连接形成。

此外，你可以假设该网格的四条边均被水包围。

题目链接

200. 岛屿数量 – 力扣（LeetCode）https://leetcode.cn/problems/number-of-islands/description/?envType=study-plan-v2&envId=top-100-liked

思路

复杂度

• 时间复杂度：O(n × m)

  • 每个格子最多被访问一次（变成 '0' 后不再访问）

  • DFS 的总调用次数等于陆地的格子数

  • 最坏情况全是陆地，需要访问所有格子

• 空间复杂度：O(n × m)

  • 最坏情况全是陆地，递归深度可能达到 n × m（但实际受栈限制）

  • 访问数组 v 的大小为 n × m

代码

class Solution {
public:
// 访问标记数组，记录格子是否被访问过
bool v[1010][1010];

// 四个方向的移动向量：下、右、上、左
int dx[4] = {1, 0, -1, 0};
int dy[4] = {0, 1, 0, -1};

int ans = 0; // 岛屿数量计数器

/**
* 深度优先搜索，将整个岛屿淹没（变成'0'）
* @param x 当前格子的行坐标
* @param y 当前格子的列坐标
* @param grid 网格引用（会被修改）
*/
void dfs(int x, int y, vector<vector<char>>& grid) {
int n = grid.size(); // 网格行数
int m = grid[0].size(); // 网格列数

// 标记当前格子已访问
v[x][y] = 1;

// 将当前陆地变成水（淹没）
if (grid[x][y] == '1') {
grid[x][y] = '0';
}

// 尝试四个方向移动
for (int i = 0; i < 4; i++) {
int xx = x + dx[i]; // 新位置的行
int yy = y + dy[i]; // 新位置的列

// 检查是否可以继续搜索：
// 1. 不能越界
// 2. 不能访问过
// 3. 不能是水（'0'）
if (xx < 0 || yy < 0 || xx >= n || yy >= m ||
v[xx][yy] || grid[xx][yy] == '0') {
continue;
}

// 递归搜索相邻陆地
dfs(xx, yy, grid);
}
}

/**
* 计算岛屿数量
* @param grid 二维字符网格
* @return 岛屿数量
*/
int numIslands(vector<vector<char>>& grid) {
int n = grid.size();
int m = grid[0].size();

// 初始化访问标记（也可以直接用grid本身标记，这里保留v数组）
memset(v, 0, sizeof(v));
ans = 0;

// 遍历整个网格
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
// 发现新岛屿（遇到'1'）
if (grid[i][j] == '1') {
ans++; // 岛屿数量加1
dfs(i, j, grid); // 淹没整个岛屿
}
}
}

return ans;
}
};