【算法面试必刷】200. 岛屿数量
目录
题目
题目链接
思路
复杂度
代码
题目
给你一个由'1'（陆地）和'0'（水）组成的的二维网格，请你计算网格中岛屿的数量。
岛屿总是被水包围，并且每座岛屿只能由水平方向和/或竖直方向上相邻的陆地连接形成。
此外，你可以假设该网格的四条边均被水包围。
题目链接
200. 岛屿数量 - 力扣（LeetCode）https://leetcode.cn/problems/number-of-islands/description/?envType=study-plan-v2&envId=top-100-liked
思路
遍历整个网格：对每个格子进行检查
发现新岛屿：如果遇到
'1'，说明发现一个新岛屿，计数器加1淹没整个岛屿：通过 DFS 把与这个
'1'相连的所有'1'都变成'0'（避免重复计数）继续遍历：直到所有格子都检查完
复杂度
时间复杂度：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; } };