代码随想录算法训练营Day44 | 99.岛屿数量、100.岛屿的最大面积

KamaCoder99.岛屿数量

99. 计数孤岛

1.思路

DFS 深搜解法

解决此问题的核心思想是DFS。当我们遍历网格时，每遇到一个未被访问过的陆地（1），就意味着发现了一个新的岛屿。此时，我们需要从这个点出发，通过DFS找到所有与它相连的陆地，并将它们全部标记为“已访问”，以避免重复计算。

方式一

main 和 dfs 分工明确。在 main 函数中发现新岛屿后，先标记起点 used[i][j] = true，再调用 dfs；dfs 函数 不处理传入的起点，只负责标记并递归访问其相邻节点。

dfs 函数的正确执行依赖于 main 函数的预处理。如果忘记在main中标记used[i][j]，可能会导致无限递归或逻辑错误。

#include <iostream> #include <vector> using namespace std; int dir[4][2]={0,-1,-1,0,0,1,1,0}; void dfs(vector<vector<int>>&graph,vector<vector<bool>>&used,int x,int y){ for(int i=0;i<4;i++){ int nextx=x+dir[i][0]; int nexty=y+dir[i][1]; if(nextx<1 || nextx>=graph.size() || nexty<1 || nexty>=graph[0].size()) continue; // 越界了，直接跳过 if(graph[nextx][nexty]==1 && !used[nextx][nexty]){ used[nextx][nexty]=true; // 只标记并访问邻居 dfs(graph,used,nextx,nexty); } } } int main(){ int n,m;cin>>n>>m; vector<vector<int>> graph(n+1,vector<int>(m+1,0)); vector<vector<bool>> used(n+1,vector<bool>(m+1,false)); for(int i=1;i<=n;i++){ for(int j=1;j<=m;j++){ cin>>graph[i][j]; } } int res=0; for(int i=1;i<=n;i++){ for(int j=1;j<=m;j++){ if(graph[i][j]==1 && !used[i][j]){ res++; // 遇到没访问过的陆地，+1 used[i][j]=true; // 关键点：main负责标记起点 dfs(graph,used,i,j); } } } cout<<res; return 0; }

方式二

dfs 高度封装。在 main 函数中发现新岛屿后，直接调用 dfs，由 dfs 内部处理标记；dfs 函数先处理传入的起点（检查、标记），再递归访问其相邻节点。

main函数只需要“发现”一个新起点，然后把整个探索任务“外包”给dfs。

dfs函数没有前置条件，自身逻辑完整，调用更安全，也更容易在其他场景中复用。

#include <iostream> #include <vector> using namespace std; int dir[4][2]={0,-1,-1,0,0,1,1,0}; void dfs(vector<vector<int>>&graph,vector<vector<bool>>&used,int x,int y){ if(graph[x][y]==0 || used[x][y]) return; // 终止条件：访问过的节点 或者 遇到海水 used[x][y]=true; // 标记访问过 for(int i=0;i<4;i++){ int nextx=x+dir[i][0]; int nexty=y+dir[i][1]; if(nextx<1 || nextx>=graph.size() || nexty<1 || nexty>=graph[0].size()) continue; dfs(graph,used,nextx,nexty); } } int main(){ int n,m;cin>>n>>m; vector<vector<int>> graph(n+1,vector<int>(m+1,0)); vector<vector<bool>> used(n+1,vector<bool>(m+1,false)); for(int i=1;i<=n;i++){ for(int j=1;j<=m;j++){ cin>>graph[i][j]; } } int res=0; for(int i=1;i<=n;i++){ for(int j=1;j<=m;j++){ if(graph[i][j]==1 && !used[i][j]){ res++; dfs(graph,used,i,j); } } } cout<<res; return 0; }

BFS 广搜解法

使用 BFS 最重要的一点就是要清楚在什么时候将一个节点标记为used=true

错误做法：从队列中取出节点时再标记。同一个节点可能被多个邻居加入队列，导致队列中出现大量重复节点，严重影响性能。

// 错误示例 while(!que.empty()){ pair<int,int> cur = que.front(); que.pop(); used[cur.first][cur.second] = true; // <-- 错误的标记时机！ for(...){ // ... 检查邻居 ... if(graph[nextx][nexty]==1 && !used[nextx][nexty]){ que.push({nextx,nexty}); // 邻居A和B可能同时看到C，并都把C加入队列 } } }

正确做法：在将节点加入队列之前就立即标记。一旦一个节点被标记，任何其他邻居再看到它时，!used[nextx][nexty]条件就不满足，从而保证了每个节点最多只被加入队列一次。

// 正确示例 if(graph[nextx][nexty]==1 && !used[nextx][nexty]){ used[nextx][nexty]=true; // <-- 1. 立即标记 que.push({nextx,nexty}); // <-- 2. 再加入队列 }

#include <iostream> #include <vector> #include <queue> using namespace std; int dir[4][2]={0,-1,-1,0,0,1,1,0}; void bfs(vector<vector<int>>&graph,vector<vector<bool>>&used,int x,int y){ queue<pair<int,int>> que; que.push({x,y}); used[x][y]=true; // 只要加入队列，立刻标记 while(!que.empty()){ pair<int,int> cur = que.front();que.pop(); for(int i=0;i<4;i++){ int nextx=cur.first+dir[i][0]; int nexty=cur.second+dir[i][1]; if(nextx<1 || nextx>=graph.size() || nexty<1 || nexty>=graph[0].size()) continue; if(graph[nextx][nexty]==1 && !used[nextx][nexty]){ used[nextx][nexty]=true; // 只要加入队列立刻标记 que.push({nextx,nexty}); } } } } int main(){ int n,m;cin>>n>>m; vector<vector<int>> graph(n+1,vector<int>(m+1,0)); vector<vector<bool>> used(n+1,vector<bool>(m+1,false)); for(int i=1;i<=n;i++){ for(int j=1;j<=m;j++){ cin>>graph[i][j]; } } int res=0; for(int i=1;i<=n;i++){ for(int j=1;j<=m;j++){ if(graph[i][j]==1 && !used[i][j]){ res++; bfs(graph,used,i,j); } } } cout<<res; return 0; }

2.思考

方式一：隐式终止条件，函数本身不包含对当前节点的终止检查，假定传入的节点是有效的。终止条件的实现是通过在递归调用之前，严格“过滤”掉所有无效的下一步来完成的。如果没有任何一个邻居满足递归条件，for循环会正常结束，函数自然返回，从而实现了终止。

方式二：显式终止条件，函数在执行任何实质性操作之前，首先检查当前状态是否满足递归继续的条件。如果不满足，就立即终止（return），不再向下执行。

3.Reference：99. 岛屿数量 | 代码随想录

KamaCoder100.最大岛屿的面积

100. 最大岛屿的面积

1.思路

DFS

写法一

隐式终止条件

DFS 处理当前节点的相邻节点，即在主函数遇到岛屿就计数为1，DFS 处理接下来的相邻陆地

#include <iostream> #include <vector> using namespace std; int res; int dir[4][2]={0,-1,-1,0,0,1,1,0}; void dfs(vector<vector<int>>&graph,vector<vector<bool>>&used,int x,int y){ for(int i=0;i<4;i++){ int nextx=x+dir[i][0]; int nexty=y+dir[i][1]; if(nextx<1 || nextx>=graph.size() || nexty<1 || nexty>=graph[0].size()) continue; if(graph[nextx][nexty]==1 && !used[nextx][nexty]){ res++; used[nextx][nexty]=true; dfs(graph,used,nextx,nexty); } } } int main(){ int n,m;cin>>n>>m; vector<vector<int>>graph(n+1,vector<int>(m+1,0)); vector<vector<bool>>used(n+1,vector<bool>(m+1,false)); int ans=0; for(int i=1;i<=n;i++){ for(int j=1;j<=m;j++){ cin>>graph[i][j]; } } for(int i=1;i<=n;i++){ for(int j=1;j<=m;j++){ if(graph[i][j]==1 && !used[i][j]){ res=1; // 因为dfs处理下一个节点，所以这里遇到陆地了就先计数，dfs处理接下来的相邻陆地 used[i][j]=true; dfs(graph,used,i,j); // 将与其链接的陆地都标记上 true ans=max(ans,res); } } } cout<<ans; return 0; }

写法二

显式终止条件

DFS 处理当前节点，即在主函数遇到岛屿就计数为0，DFS 处理接下来的全部陆地

#include <iostream> #include <vector> using namespace std; int res; int dir[4][2]={0,-1,-1,0,0,1,1,0}; void dfs(vector<vector<int>>&graph,vector<vector<bool>>&used,int x,int y){ if(graph[x][y]==0 || used[x][y]) return; used[x][y]=1; // 标记访问过 res++; for(int i=0;i<4;i++){ int nextx=x+dir[i][0]; int nexty=y+dir[i][1]; if(nextx<1 || nextx>=graph.size() || nexty<1 || nexty>=graph[0].size()) continue; dfs(graph,used,nextx,nexty); } } int main(){ int n,m;cin>>n>>m; vector<vector<int>>graph(n+1,vector<int>(m+1,0)); vector<vector<bool>>used(n+1,vector<bool>(m+1,false)); int ans=0; for(int i=1;i<=n;i++){ for(int j=1;j<=m;j++){ cin>>graph[i][j]; } } for(int i=1;i<=n;i++){ for(int j=1;j<=m;j++){ if(graph[i][j]==1 && !used[i][j]){ res=0; // 因为dfs处理当前节点，所以遇到陆地计数为0，进dfs之后在开始从1计数 dfs(graph,used,i,j); // 将与其链接的陆地都标记上 true ans=max(ans,res); } } } cout<<ans; return 0; }

BFS

每次开始探索一个新的岛屿时，面积计数器都会从1开始重新计算

#include <iostream> #include <vector> #include <queue> using namespace std; int res; int dir[4][2]={0,-1,-1,0,0,1,1,0}; void bfs(vector<vector<int>>&graph,vector<vector<bool>>&used,int x,int y){ queue<pair<int,int>>que; que.push({x,y}); used[x][y]=true; // 加入队列就意味节点是陆地可到达的点 while(!que.empty()){ pair<int,int> cur=que.front();que.pop(); for(int i=0;i<4;i++){ int nextx=cur.first+dir[i][0]; int nexty=cur.second+dir[i][1]; if(nextx<1 || nextx>=graph.size() || nexty<1 || nexty>=graph[0].size()) continue; if(graph[nextx][nexty]==1 && !used[nextx][nexty]){ res++; used[nextx][nexty]=true; que.push({nextx,nexty}); } } } } int main(){ int n,m;cin>>n>>m; vector<vector<int>>graph(n+1,vector<int>(m+1,0)); vector<vector<bool>>used(n+1,vector<bool>(m+1,false)); int ans=0; for(int i=1;i<=n;i++){ for(int j=1;j<=m;j++){ cin>>graph[i][j]; } } for(int i=1;i<=n;i++){ for(int j=1;j<=m;j++){ if(graph[i][j]==1 && !used[i][j]){ res=1; bfs(graph,used,i,j); // 将与其链接的陆地都标记上 true ans=max(ans,res); } } } cout<<ans; return 0; }

2.思考

这道题在 岛屿数量 这道题上整体思路没有变化，只是把计算的岛屿数量改成了计算最大的某个岛屿，思路还是很清晰的，重点掌握 DFS 的两种解法，要么使用隐式终止条件，要么使用显式终止条件，二者在主函数中调用前 res 的初始化也是不同的。

3.Reference：100. 岛屿的最大面积 | 代码随想录