代码随想录算法训练营第五十二天|图论part3

101. 孤岛的总面积

题目链接：101. 孤岛的总面积

文章讲解：代码随想录

思路：

与岛屿面积差不多，区别是再dfs的时候，如果碰到越界的，需要用一个符号标记这不是孤岛再continue

#include <iostream>
#include <vector>
using namespace std;int dir[4][2]={{0,1},{0,-1},{1,0},{-1,0}};
void dfs(vector<vector<int>>graph,vector<vector<bool>>&visited,int &area,int x,int y,bool& isGudao){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()){isGudao=false;  //标记不是孤岛continue;}if(graph[nextx][nexty]&&!visited[nextx][nexty]){   //发现岛屿      area++;visited[nextx][nexty]=true;dfs(graph,visited,area,nextx,nexty,isGudao);    }}
}int main(){int n,m;cin>>n>>m;vector<vector<int>>graph(n+1,vector<int>(m+1,0));for(int i=1;i<=n;i++){for(int j=1;j<=m;j++){cin>>graph[i][j];}}int result=0;vector<vector<bool>>visited(n+1,vector<bool>(m+1,false));for(int i=1;i<=n;i++){for(int j=1;j<=m;j++){if(graph[i][j]&&!visited[i][j]){   //发现岛屿visited[i][j]=true;int area=1;bool isGudao=true;dfs(graph,visited,area,i,j,isGudao);if(isGudao)result+=area;}}}cout<<result<<endl;
}

102. 沉没孤岛

题目链接：102. 沉没孤岛

文章讲解：代码随想录

思路：

与上体差不多，添加一个变量record  本次深搜或广搜遍历到的岛屿

main函数中dfs结束后 得到是不是孤岛 如果是孤岛 record里的坐标全部标为0 

#include <iostream>
#include <vector>
using namespace std;int dir[4][2]={{0,1},{0,-1},{1,0},{-1,0}};
void dfs(vector<vector<int>>graph,vector<vector<bool>>&visited,int x,int y,bool& isGudao,vector<pair<int,int>>&record){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()){isGudao=false;continue;}if(graph[nextx][nexty]&&!visited[nextx][nexty]){   //发现岛屿      visited[nextx][nexty]=true;record.push_back({nextx,nexty});dfs(graph,visited,nextx,nexty,isGudao,record);    }}
}int main(){int n,m;cin>>n>>m;vector<vector<int>>graph(n+1,vector<int>(m+1,0));for(int i=1;i<=n;i++){for(int j=1;j<=m;j++){cin>>graph[i][j];}}vector<vector<bool>>visited(n+1,vector<bool>(m+1,false));for(int i=1;i<=n;i++){for(int j=1;j<=m;j++){if(graph[i][j]&&!visited[i][j]){   //发现岛屿visited[i][j]=true;vector<pair<int,int>>record;   //记录本片岛屿record.push_back({i,j});bool isGudao=true;dfs(graph,visited,i,j,isGudao,record);if(isGudao){for(int k=0;k<record.size();k++){graph[record[k].first][record[k].second]=0;}}}}}//输出for(int i=1;i<=n;i++){for(int j=1;j<m;j++){cout<<graph[i][j]<<' ';}cout<<graph[i][m]<<endl;}
}

题目链接:103. 水流问题

文章讲解：创作中心-CSDN

思路：

用逆向思维，从第一边界出发，水往高处流看能经过哪些节点

从第二边界出发，水往高处流 看能经过哪些节点

然后求第一边界出发经过的节点与第二边界出发经过的节点的交集

#include <iostream>
#include <vector>
using namespace std;int dir[4][2]={{-1,0},{1,0},{0,1},{0,-1}};
void dfs(vector<vector<int>>graph,vector<vector<bool>>&record,int x,int y){record[x][y]=true;for(int i=0;i<4;i++){int nextx=x+dir[i][0];int nexty=y+dir[i][1];if(nextx<0||nextx>=graph.size()||nexty<0||nexty>=graph[0].size()){continue;}if(!record[nextx][nexty]&&graph[nextx][nexty]>=graph[x][y]){dfs(graph,record,nextx,nexty);}}}int main(){int n,m;cin>>n>>m;vector<vector<int>>graph(n,vector<int>(m,0));for(int i=0;i<n;i++){for(int j=0;j<m;j++){cin>>graph[i][j];}}vector<vector<bool>>record1(n,vector<bool>(m,false));vector<vector<bool>>record2(n,vector<bool>(m,false));//从第一边界出发for(int i=0;i<n;i++){dfs(graph,record1,i,0);}for(int j=0;j<m;j++){dfs(graph,record1,0,j);}//从第二边界出发for(int i=0;i<n;i++){dfs(graph,record2,i,m-1);}for(int j=0;j<m;j++){dfs(graph,record2,n-1,j);}//求交for(int i=0;i<n;i++){for(int j=0;j<m;j++){if(record1[i][j]&&record2[i][j]){cout<<i<<' '<<j<<endl;}}}}

思路：

第一步 统计每块岛屿的面积

第二步 遍历所有海洋 相邻岛屿面积加起来 

求最大值

set查找用count

插入用insert

还要考虑全陆地的情况

 

#include <iostream>
#include <vector>
#include <unordered_map>
#include <unordered_set>using namespace std;
int dir[4][2]={{-1,0},{1,0},{0,1},{0,-1}};void dfs(vector<vector<int>>&graph,vector<vector<bool>>&visited,int x,int y,int mark,int &count){visited[x][y]=true;count++;graph[x][y]=mark;for(int i=0;i<4;i++ ){int nextx=x+dir[i][0];int nexty=y+dir[i][1];if (nextx<0 || nexty<0 || nextx >=graph.size() || nexty>=graph[0].size())continue;if(!visited[nextx][nexty]&&graph[nextx][nexty]!=0){dfs(graph,visited,nextx,nexty,mark,count);}}
}int main(){int n,m;cin>>n>>m;vector<vector<int>>graph(n,vector<int>(m,0));for(int i=0;i<n;i++){for(int j=0;j<m;j++){cin>>graph[i][j];}}//统计每块岛屿的面积  并且每块岛屿赋予一个编号vector<vector<bool>>visited(n,vector<bool>(m,0));int mark=2;unordered_map<int,int>mymap;bool isAllGrid=true;for(int i=0;i<n;i++){for(int j=0;j<m;j++){int count=0;if(graph[i][j]==0)isAllGrid=false;if(!visited[i][j]&&graph[i][j]==1){dfs(graph,visited,i,j,mark,count);mymap[mark] = count; mark++;}}}//遍历所有海洋  统计海洋相邻岛屿信息int result=0;unordered_set<int>myset;for(int i=0;i<n;i++){for(int j=0;j<m;j++){myset.clear();if(graph[i][j]==0){int currentRes=0;for(int k=0;k<4;k++){int nextx=i+dir[k][0];int nexty=j+dir[k][1];if(nextx<0||nexty<0||nextx>=graph.size()||nexty>graph[0].size()) continue;if(!myset.count(graph[nextx][nexty])&&graph[nextx][nexty]!=0){currentRes+=mymap[graph[nextx][nexty]];myset.insert(graph[nextx][nexty]);   result=max(result,currentRes);}}}}}if(isAllGrid){cout<<n*m;}else{cout<<result+1;}return 0;}