笔记：代码随想录算法训练营day58：101.孤岛的总面积、102.沉没孤岛、103.水流问题、104.建造最大岛屿

学习资料：代码随想录

文中含大模型生成内容

101. 孤岛的总面积

卡码网：101. 孤岛的总面积

所以找周边都是水的陆地的方法就是找边缘的陆地然后删除它连同它的连通的陆地

深搜
 

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

广搜
 

#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>>& fiji,int x,int y){fiji[x][y]=0;queue<pair<int,int>> que;que.push({x,y});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>=fiji.size()||ynext<0||ynext>=fiji[0].size()) continue;if(fiji[xnext][ynext]==1){que.push({xnext,ynext});fiji[xnext][ynext]=0;}}}
}
int main(){int n,m;cin>>n>>m;vector<vector<int>> fiji(n,vector<int>(m,0));for(int i=0;i<n;i++){for(int j=0;j<m;j++){cin>>fiji[i][j];}}for(int i=0;i<n;i++){if(fiji[i][0]==1){bfs(fiji,i,0);}if(fiji[i][m-1]==1){bfs(fiji,i,m-1);}}for(int j=0;j<m;j++){if(fiji[0][j]==1){bfs(fiji,0,j);}if(fiji[n-1][j]==1){bfs(fiji,n-1,j);}}int count =0;for(int i=0;i<n;i++){for(int j=0;j<m;j++){if(fiji[i][j]==1) count++;}}cout<<count<<endl;
}

在 深度优先搜索（DFS）或广度优先搜索（BFS） 中，我们通常用 visited 数组来标记已经访问过的点，以防止：

• 重复访问，导致超时
• 无限递归，导致栈溢出（Stack Overflow）

通常如果 不能修改原数组，我们就要 额外开一个 visited 数组 来记录访问情况。

这里的 grid 只有两种值：

• 1（陆地）
• 0（海洋）

我们遍历 grid 时：

1. 遇到 1（陆地）：

   • 说明它是未访问过的，然后我们调用 dfs(grid, x, y) 。
   • 在 DFS 里，我们把 grid[x][y] 直接改成 0，代表这个点已经被访问过了。
   • 这样，我们就不会 重复访问 这个点，也不会影响后续的 DFS 逻辑。

2. 遇到 0（海洋）：

   • 要么是原始的海洋
   • 要么是 DFS 过程中被修改成 0 的陆地
   • 不需要再访问，所以直接跳过

3. 这样，我们实际上是用 grid 自己充当 visited 数组！

102. 沉没孤岛

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

先把边缘的陆地标记成2，然后把陆地1改成水0，最后把边缘的陆地改回1就可以了

深搜

#include <iostream>
#include <vector>
using namespace std;int dir[4][2]={0,1,-1,0,0,-1,1,0};
void dfs(vector<vector<int>>& fiji,int x,int y){fiji[x][y]=2;for(int i=0;i<4;i++){int xnext = x+dir[i][0];int ynext = y+dir[i][1];if(xnext<0||xnext>=fiji.size()||ynext<0||ynext>=fiji[0].size()) continue;if(fiji[xnext][ynext]==1){dfs(fiji,xnext,ynext);}}
}
int main(){int n,m;cin>>n>>m;vector<vector<int>> fiji(n,vector<int>(m,0));for(int i=0;i<n;i++){for(int j=0;j<m;j++){cin>>fiji[i][j];}}for(int i=0;i<n;i++){if(fiji[i][0]==1) dfs(fiji,i,0);if(fiji[i][m-1]==1) dfs(fiji,i,m-1);}for(int j=0;j<m;j++){if(fiji[0][j]==1) dfs(fiji,0,j);if(fiji[n-1][j]==1) dfs(fiji,n-1,j);}for(int i=0;i<n;i++){for(int j=0;j<m;j++){if(fiji[i][j]==2){fiji[i][j]=1;}else if(fiji[i][j]==1){fiji[i][j]=0;}cout<<fiji[i][j]<<' ';}cout<<endl;}}

 广搜

#include <iostream>
#include <vector>
#include <queue>
using namespace std;int dir[4][2]={0,1,-1,0,0,-1,1,0};
void dfs(vector<vector<int>>& fiji,int x,int y){queue<pair<int,int>> que;que.push({x,y});fiji[x][y]=2;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>=fiji.size()||ynext<0||ynext>=fiji[0].size()) continue;if(fiji[xnext][ynext]==1){que.push({xnext,ynext});fiji[xnext][ynext]=2;}}}
}
int main(){int n,m;cin>>n>>m;vector<vector<int>> fiji(n,vector<int>(m,0));for(int i=0;i<n;i++){for(int j=0;j<m;j++){cin>>fiji[i][j];}}for(int i=0;i<n;i++){if(fiji[i][0]==1) dfs(fiji,i,0);if(fiji[i][m-1]==1) dfs(fiji,i,m-1);}for(int j=0;j<m;j++){if(fiji[0][j]==1) dfs(fiji,0,j);if(fiji[n-1][j]==1) dfs(fiji,n-1,j);}for(int i=0;i<n;i++){for(int j=0;j<m;j++){if(fiji[i][j]==2){fiji[i][j]=1;}else if(fiji[i][j]==1){fiji[i][j]=0;}cout<<fiji[i][j]<<' ';}cout<<endl;}}

103. 水流问题

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

从边缘向中间搜索高点并记录

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

一点小思考：第一种写法可否把visited改成全局变量然后时间复杂度也变成n*m？还是从两边往中间走合适，要不然使用全局visited并且还是用第一种方法遍历每一个点的话，遇到{{{2,2,2},{2,1,2}{2,2,2}}，岂不是中间这个1也会被标记成true，这里是自己的思考，欢迎批评指正

104.建造最大岛屿

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

需要先遍历一遍给每块岛一个序号，记录数量，然后去搜索水域加上周围的岛，取最大值，

其中，岛的序号和面积用unordered_map记录

有一个有趣的一点是水周围的陆地可能是连在一起的，所以也要加上后就记录一下，用unordered_set记录

#include <iostream>
#include <vector>
#include <unordered_map>
#include <unordered_set>
using namespace std;int dir[4][2]={0,1,-1,0,0,-1,1,0};void dfs(vector<vector<int>>& fiji,vector<vector<bool>>& visited,int x,int y,int& mark,int& count){if(visited[x][y]==true) return;fiji[x][y]=mark;visited[x][y]=true;count++;for(int i=0;i<4;i++){int xnext = x+dir[i][0];int ynext = y+dir[i][1];if(xnext<0||xnext>=fiji.size()||ynext<0||ynext>=fiji[0].size()) continue;if(fiji[xnext][ynext]==0) continue;if(visited[xnext][ynext]==false&&fiji[xnext][ynext]==1){dfs(fiji,visited,xnext,ynext,mark,count);}}
}
int main(){int n,m;cin>>n>>m;vector<vector<int>> fiji(n,vector<int>(m,0));for(int i=0;i<n;i++){for(int j=0;j<m;j++){cin>>fiji[i][j];}}vector<vector<bool>> visited(n,vector<bool>(m,0));int mark=2;bool isLand = true;unordered_map<int,int> map;for(int i=0;i<n;i++){for(int j=0;j<m;j++){if(fiji[i][j]==0) isLand=false;if(fiji[i][j]==1&&visited[i][j]==false){int count=0;dfs(fiji,visited,i,j,mark,count);map[mark]=count;mark++;}}}if(isLand==true){cout<<n*m;return 0;}int result =0;int area=0;unordered_set<int> addedArea;for(int i=0;i<n;i++){for(int j=0;j<m;j++){addedArea.clear();if(fiji[i][j]==0){area = 0;for(int k=0;k<4;k++){int inext=dir[k][0]+i;int jnext=dir[k][1]+j;if(inext<0||inext>=fiji.size()||jnext<0||jnext>=fiji[0].size()) continue;if(addedArea.count(fiji[inext][jnext])!=0) continue;area+=map[fiji[inext][jnext]];addedArea.insert(fiji[inext][jnext]);}}result=max(area,result);}}cout<<result+1<<endl;
}

.