【力扣100题】64.岛屿数量

题目描述

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

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

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

示例

示例 1： 输入：grid = [ ['1','1','1','1','0'], ['1','1','0','1','0'], ['1','1','0','0','0'], ['0','0','0','0','0'] ] 输出：1 示例 2： 输入：grid = [ ['1','1','0','0','0'], ['1','1','0','0','0'], ['0','0','1','0','0'], ['0','0','0','1','1'] ] 输出：3

提示：

• m == grid.length
• n == grid[i].length
• 1 <= m, n <= 300
• grid[i][j] 的值为 ‘0’ 或 ‘1’

解题思路总览

一、核心解法：DFS（深度优先搜索）

核心思想

遍历整个网格，遇到未访问的陆地 ‘1’ 时，就找到了一个新岛屿，然后从这个位置出发，深度优先搜索把所有相邻的陆地都标记为已访问。

核心步骤： 1. 遍历网格每个位置 2. 遇到未访问的 '1'，岛屿数 +1 3. 从该位置出发 DFS，标记所有相连的 '1' 4. 继续遍历，重复上述过程

关键洞察

为什么 DFS 能解决问题？ 因为岛屿的定义是：相邻（上下左右）的陆地连成的区域。 当我们找到一个未访问的陆地 '1' 时： - 它是一个新岛屿的起点 - 通过 DFS 可以找到所有和它相连的陆地 - 这些陆地都属于同一个岛屿 遍历完成后，所有陆地都被标记，岛屿数量就是答案。

图解

grid = [ ['1','1','1','1','0'], ['1','1','0','1','0'], ['1','1','0','0','0'], ['0','0','0','0','0'] ] 遍历过程： 初始: visited 全部为 false ans = 0 (i=0, j=0): grid[0][0]='1', 未访问 ans = 1 DFS(0,0): 标记 [0,0],[0,1],[0,2],[0,3],[1,0],[1,1],[1,2],[2,0],[2,1],[2,2] visited: 第一行全标记，第二行前两列标记，第三行前两列标记 (i=0, j=1-3): 已被访问，跳过 (i=0, j=4): '0'，跳过 (i=1, j=0-4): 已被访问，跳过 (i=2, j=0-4): 已被访问，跳过 (i=3, j=0-4): 全为 '0'，跳过 输出: ans = 1

grid = [ ['1','1','0','0','0'], ['1','1','0','0','0'], ['0','0','1','0','0'], ['0','0','0','1','1'] ] 遍历过程： 初始: visited 全部为 false ans = 0 (i=0, j=0): grid[0][0]='1', 未访问 ans = 1 DFS(0,0): 标记 [0,0],[0,1],[1,0],[1,1] visited: 左上角 2x2 区域 (i=0, j=2-4): '0' 或已访问，跳过 (i=1, j=2-4): 跳过 (i=2, j=0-1): '0'，跳过 (i=2, j=2): grid[2][2]='1', 未访问 ans = 2 DFS(2,2): 标记 [2,2] (i=2, j=3-4): 已访问或 '0' (i=3, j=0-2): '0'，跳过 (i=3, j=3): grid[3][3]='1', 未访问 ans = 3 DFS(3,3): 标记 [3,3],[3,4] visited: 右下角 2x2 区域 输出: ans = 3

二、算法流程图

输入: grid = [ ['1','1','1'], ['1','1','0'], ['0','0','1'] ] 初始化: visited = [[false,false,false], [false,false,false], [false,false,false]] ans = 0 dir = [[-1,0],[0,-1],[1,0],[0,1]] // 上左下右 遍历 (i=0, j=0): grid[0][0]='1', visited[0][0]=false ans = 1 DFS(0,0): visited[0][0]=true 尝试上: i=-1, 越界 尝试左: j=-1, 越界 尝试下: (1,0)='1', 未访问 -> DFS(1,0) visited[1][0]=true 上下左右探索 -> 递归到 (0,0), (2,0), (1,1) 尝试右: (0,1)='1', 未访问 -> DFS(0,1) visited[0][1]=true 继续探索... 遍历完成: ans = 2 (两个岛屿) 输出: 2

三、完整代码实现

classSolution{public:intnumIslands(vector<vector<char>>&grid){if(grid.empty())return0;intm=grid.size();intn=grid[0].size();vector<vector<bool>>visited(m,vector<bool>(n,false));// 方向：上、左、下、右intdir[4][2]={{-1,0},{0,-1},{1,0},{0,1}};function<void(int,int)>dfs=[&](inti,intj){// 如果已经访问过，直接返回if(visited[i][j])return;// 标记为已访问visited[i][j]=true;// 尝试四个方向for(intk=0;k<4;k++){intii=i+dir[k][0];intjj=j+dir[k][1];// 检查越界和是否为陆地if(ii<0||ii>=m||jj<0||jj>=n)continue;if(grid[ii][jj]=='0')continue;// 递归搜索dfs(ii,jj);}};intans=0;// 遍历整个网格for(inti=0;i<m;i++){for(intj=0;j<n;j++){// 找到未访问的陆地，就是新岛屿if(grid[i][j]=='1'&&!visited[i][j]){ans++;dfs(i,j);}}}returnans;}};

四、逐行解析

if(grid.empty())return0;

• 处理空网格的特殊情况

intm=grid.size();intn=grid[0].size();vector<vector<bool>>visited(m,vector<bool>(n,false));

• m, n：网格的行数和列数
• visited：记录每个位置是否被访问过

intdir[4][2]={{-1,0},{0,-1},{1,0},{0,1}};

• 四个方向的偏移量：上、左、下、右

function<void(int,int)>dfs=[&](inti,intj){

• 定义 DFS 函数，用 lambda 方便递归调用

if(visited[i][j])return;visited[i][j]=true;

• 如果已经访问过，直接返回（避免重复访问）
• 否则标记为已访问

for(intk=0;k<4;k++){intii=i+dir[k][0];intjj=j+dir[k][1];if(ii<0||ii>=m||jj<0||jj>=n)continue;if(grid[ii][jj]=='0')continue;dfs(ii,jj);}

• 遍历四个方向
• 越界检查和是否为陆地的检查
• 递归搜索相邻的陆地

if(grid[i][j]=='1'&&!visited[i][j]){ans++;dfs(i,j);}

• 如果遇到未访问的陆地，说明发现了新岛屿
• ans++，然后从该位置开始 DFS 标记整个岛屿

五、DFS 的原理

DFS 的核心思想：沿着一条路走到底，然后回溯。 对于岛屿问题： 1. 从起点出发，把起点标记为已访问 2. 依次尝试四个方向 3. 如果相邻位置是未访问的陆地，递归进入 4. 每个位置只会被访问一次 类似"染色"的过程： - 找到一个未染色陆地，染成新颜色 - 递归把所有相邻的陆地染成同样的颜色 - 继续找下一个未染色陆地

六、与并查集对比

七、复杂度分析

详细分析：

时间复杂度： 每个格子最多被访问一次 每次访问时进行常数次操作 总计：O(m*n) 空间复杂度： visited 数组：O(m*n) 递归栈深度：最坏 O(m*n)（当整个网格都是陆地时） 总计：O(m*n)

八、边界情况分析

示例：全是水

grid = [ ['0','0','0'], ['0','0','0'] ] 遍历： 所有位置都是 '0'，不满足 grid[i][j] == '1' ans = 0 输出: 0

示例：全是陆地

grid = [ ['1','1','1'], ['1','1','1'] ] 遍历： (0,0): 发现新岛屿，ans=1，DFS 标记整个网格 剩余位置都已访问 输出: 1

九、面试追问 FAQ

十、相关题目

十一、总结

岛屿数量是经典的连通区域问题，通过 DFS/BFS 遍历网格，标记已访问的陆地，统计连通区域的数量。