笔记：代码随想录算法训练营day57：99.岛屿数量 深搜、岛屿数量 广搜、100.岛屿的最大面积

学习资料：代码随想录

注：文中含大模型生成内容

99. 岛屿数量

卡码网题目链接（ACM模式）

先看深搜方法：找到未标标记过的说明找到一片陆地的或者一片陆地的一个角落，dfs搜索是寻找相连接的陆地其余部分并做好标记

#include <iostream>
#include <vector>
using namespace std;int direction[4][2]={0,1,-1,0,0,-1,1,0};void dfs(const vector<vector<int>>& B612,vector<vector<bool>>& visited,int x,int y){  //visited数组不能被声明为const,因为要改动int nextx,nexty;for(int i=0;i<4;i++){              //无需终止条件，在递归函数中，当当前调用的所有循环（或所有条件分支）都处理完后，函数会自动返回到上一级的调用处。这就是递归调用栈的工作方式nextx=direction[i][0]+x;nexty=direction[i][1]+y;if(nextx>=B612.size() || nextx<0 || nexty>=B612[0].size() || nexty<0) continue;else if(visited[nextx][nexty]==false&&B612[nextx][nexty]==1){visited[nextx][nexty]=true;dfs(B612,visited,nextx,nexty);}}
}int main(){int N,M;cin>>N>>M;  //要有先输入参数再建立数组的意识vector<vector<int>> B612(N,vector<int>(M,0));for(int i=0;i<N;i++){for(int j=0;j<M;j++){cin>>B612[i][j];}}vector<vector<bool>> visited(N,vector<bool>(M,false));int result=0;
// 查找陆地过程for(int i=0;i<N;i++){for(int j=0;j<M;j++){if(B612[i][j]==1&&!visited[i][j]){   //遇到未访问过的陆地result++;visited[i][j]=true;dfs(B612,visited,i,j);           //递归查找相连的陆地}}}cout<<result<<endl;
}

深搜还有第二种写法，加上了终止条件，此时就不能在深搜函数之前判断并修改visited了，这样会到达终止条件。正确做法为判断为到达终止条件后再修改visited。这样在dfs函数内部调用自己之前也就不用修改visited了，统一在调用函数初期修改

#include <iostream>
#include <vector>
using namespace std;int direction[4][2]={0,1,-1,0,0,-1,1,0};void dfs(const vector<vector<int>>& B612,vector<vector<bool>>& visited,int x,int y){  //visited数组不能被声明为const,因为要改动if(visited[x][y]==true || B612[x][y]==0) return;visited[x][y]=true;int nextx,nexty;for(int i=0;i<4;i++){              nextx=direction[i][0]+x;nexty=direction[i][1]+y;if(nextx>=B612.size() || nextx<0 || nexty>=B612[0].size() || nexty<0) continue;dfs(B612,visited,nextx,nexty);}
}int main(){int N,M;cin>>N>>M;  //要有先输入参数再建立数组的意识vector<vector<int>> B612(N,vector<int>(M,0));for(int i=0;i<N;i++){for(int j=0;j<M;j++){cin>>B612[i][j];}}vector<vector<bool>> visited(N,vector<bool>(M,false));int result=0;
// 查找陆地过程for(int i=0;i<N;i++){for(int j=0;j<M;j++){if(B612[i][j]==1&&!visited[i][j]){   //遇到未访问过的陆地result++;// visited[i][j]=true;dfs(B612,visited,i,j);           //递归查找相连的陆地}}}cout<<result<<endl;
}

广搜需要显性借助队列来记录一下，深搜是隐形地使用栈

#include <iostream>
#include <vector>
#include <queue>
using namespace std;
int dir[4][2]={0,1,-1,0,0,-1,1,0};
void bfs(const vector<vector<int>>& B612,vector<vector<bool>>& visited,int x,int y){queue<pair<int,int>> que;que.push({x,y});visited[x][y]=true;int xnext,ynext;while(!que.empty()){pair<int,int> cur;cur = que.front();que.pop(); for(int i=0;i<4;i++){xnext=cur.first+dir[i][0];ynext=cur.second+dir[i][1];if(xnext<0||xnext>=B612.size()||ynext<0||ynext>=B612[0].size()) continue;if(visited[xnext][ynext]==false&&B612[xnext][ynext]==1){que.push({xnext,ynext});visited[xnext][ynext]=true;}}}
}
int main(){int N,M;cin>>N>>M;vector<vector<int>> B612(N,vector<int>(M,0));for(int i=0;i<N;i++){for(int j=0;j<M;j++){cin>>B612[i][j];}}vector<vector<bool>> visited(N,vector<bool>(M,0));int result = 0;for(int i=0;i<N;i++){for(int j=0;j<M;j++){if(B612[i][j]==1&&visited[i][j]==false){result++;bfs(B612,visited,i,j);}}}cout<<result<<endl;
}

注意广搜的visited的操作时机，在每一次push之后 

99. 岛屿数量

卡码网题目链接（ACM模式）

同样还是两种深搜写法和一种广搜写法，

#include <iostream>
#include <vector>
using namespace std;int dir[4][2]={0,1,-1,0,0,-1,1,0};
int count;void dfs(const vector<vector<int>>& maldives,vector<vector<bool>>& visited,int x,int y){int xnext,ynext;for(int i=0;i<4;i++){xnext=x+dir[i][0];ynext=y+dir[i][1];if(xnext>=maldives.size()||xnext<0||ynext>=maldives[0].size()||ynext<0) continue;if(visited[xnext][ynext]==false&&maldives[xnext][ynext]==1){count++;visited[xnext][ynext]=true;dfs(maldives,visited,xnext,ynext);}}
}int main(){int m,n;cin>>n>>m;vector<vector<int>> maldives(n,vector<int>(m,0));for(int i=0;i<n;i++){for(int j=0;j<m;j++){cin>>maldives[i][j];}}vector<vector<bool>> visited(n,vector<bool>(m,0));int result =0;for(int i=0;i<n;i++){for(int j=0;j<m;j++){if(maldives[i][j]==1&&visited[i][j]==false){count=1;visited[i][j]=true;dfs(maldives,visited,i,j);result=max(count,result);//cout<<result<<endl;}}}cout<<result<<endl;
}

#include <iostream>
#include <vector>
using namespace std;int dir[4][2]={0,1,-1,0,0,-1,1,0};
int count;void dfs(const vector<vector<int>>& maldives,vector<vector<bool>>& visited,int x,int y){if(visited[x][y]==true||maldives[x][y]==0) return;visited[x][y]=true;count++;int xnext,ynext;for(int i=0;i<4;i++){xnext=x+dir[i][0];ynext=y+dir[i][1];if(xnext>=maldives.size()||xnext<0||ynext>=maldives[0].size()||ynext<0) continue;//count++;//visited[xnext][ynext]=true;dfs(maldives,visited,xnext,ynext);}
}int main(){int m,n;cin>>n>>m;vector<vector<int>> maldives(n,vector<int>(m,0));for(int i=0;i<n;i++){for(int j=0;j<m;j++){cin>>maldives[i][j];}}vector<vector<bool>> visited(n,vector<bool>(m,0));int result =0;for(int i=0;i<n;i++){for(int j=0;j<m;j++){if(maldives[i][j]==1&&visited[i][j]==false){count=0;//visited[i][j]=true;dfs(maldives,visited,i,j);result=max(count,result);}}}cout<<result<<endl;
}

注意count的操作和visited是在一起的，即找到后，标记+记录

#include <iostream>
#include <vector>
#include <queue>
using namespace std;int dir[4][2]={0,1,-1,0,0,-1,1,0};
int count;void bfs(const vector<vector<int>>& maldives,vector<vector<bool>>& visited,int x,int y){queue<pair<int,int>> que;que.push({x,y});visited[x][y]=true;count++;while(!que.empty()){pair<int,int> cur = que.front();que.pop();for(int i=0;i<4;i++){int xnext=cur.first+dir[i][0];int ynext=cur.second+dir[i][1];if(xnext<0||xnext>=maldives.size()||ynext<0||ynext>=maldives[0].size()) continue;if(visited[xnext][ynext]==false&&maldives[xnext][ynext]==1){que.push({xnext,ynext});visited[xnext][ynext]=true;count++;}}}
}int main(){int m,n;cin>>n>>m;vector<vector<int>> maldives(n,vector<int>(m,0));for(int i=0;i<n;i++){for(int j=0;j<m;j++){cin>>maldives[i][j];}}vector<vector<bool>> visited(n,vector<bool>(m,0));int result =0;for(int i=0;i<n;i++){for(int j=0;j<m;j++){if(maldives[i][j]==1&&visited[i][j]==false){count=0;//visited[i][j]=true;bfs(maldives,visited,i,j);result=max(count,result);}}}cout<<result<<endl;
}

 深搜两种写法的区别：

• 在版本二中，dfs 函数自身判断当前结点是否满足递归条件，如果不满足则立即返回，这就保证了每个进入 dfs 的结点都一定被计数一次。
• 而在版本一中，dfs 函数假定传入的结点已经被处理（已经标记和计数），它只关注于后续的邻居。

加上返回条件后，你让 DFS 函数自己负责判断当前节点是否有效并进行标记和计数，这就改变了 DFS 的“契约”。

• 原来的写法（版本一）：
  调用者（主函数）已经预先判断、标记并计数了起始节点，所以 DFS 只处理“邻居”。因此，DFS 函数没有对传入的节点再做一次有效性检查，也不会再重复计数。

• 加上返回条件的写法（版本二）：
  你让 DFS 函数在入口处立即检查：如果当前节点已经访问过或者是水（无效），就直接返回；否则，立即标记并计数。
  这样做使得 DFS 成为一个更“通用”的函数，可以被任意调用，而不必依赖调用者事先处理。
  但这也意味着主函数不应在调用 DFS 前预先计数，否则就会重复计数。

简单说，加上返回条件后，DFS 的职责就从“仅扩展邻居”变为“全权负责当前节点及其邻居的处理”，这就要求你调整计数逻辑和调用方式，确保每个节点只被处理和计数一次。

换句话说，加入返回条件改变了函数的接口和行为约定（契约），因此需要相应地改变代码结构

假如想又有终止条件又提前处理，冲突点在于：

如果你混用两种做法，即在主函数中预先判断和标记 A，又在 DFS 中加入终止条件判断，就会出现以下两种潜在问题：

1. 重复计数（双重处理）：

   • 假设主函数预先对 A 标记并计数，然后调用 DFS(A)。
   • DFS 入口处检查到 visited[A] 已经为 true（因为主函数预先标记了），那么 DFS 立即返回，不再扩展 A 的邻居。
   • 结果：A 的邻居没有被搜索到，整个岛屿可能无法正确计数。

   或者反过来，如果你不预先标记但又在 DFS 内部计数，而主函数又对 A 进行了计数，就会导致 A 被计数两次。

2. 跳过递归扩展：

   • 如果你预先标记了 A，而 DFS 又有 if(visited[x][y] ...) return; 的终止条件，那么当 DFS 被调用时，它会发现 A 已经被标记，然后直接返回，不会继续对 A 的邻居进行递归调用。
   • 这会使得整个 DFS 搜索提前终止，导致岛屿中的其他陆地节点被遗漏，计数结果不正确。