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

目录题目题目链接思路复杂度代码题目给你一个由1陆地和0水组成的的二维网格请你计算网格中岛屿的数量。岛屿总是被水包围并且每座岛屿只能由水平方向和/或竖直方向上相邻的陆地连接形成。此外你可以假设该网格的四条边均被水包围。题目链接200. 岛屿数量 - 力扣LeetCodehttps://leetcode.cn/problems/number-of-islands/description/?envTypestudy-plan-v2envIdtop-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, vectorvectorchar 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(vectorvectorchar 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; } };