代码随想录算法训练营 | 图论 | 孤岛总面积、沉没孤岛

101. 孤岛的总面积//思路大概是先计算面积，然后如果有接触路面就返回false。可能稍微多余算了太多无用面积。

#include<bits/stdc++.h>
using namespace std;
void sum(vector<vector<bool>>& finded,const vector<vector<int>>& graph,int a,int b,int& result,bool& Ifisland){if(a<0||b<0||a>graph.size()-1||b>graph[0].size()-1) return;else if(finded[a][b]==true) return;else if(graph[a][b]==0){finded[a][b]=true;return;}else {finded[a][b]=true;result++;if(a==0||b==0||a==graph.size()-1||b==graph[0].size()-1) Ifisland=false;sum(finded,graph,a+1,b,result,Ifisland);sum(finded,graph,a,b+1,result,Ifisland);sum(finded,graph,a-1,b,result,Ifisland);sum(finded,graph,a,b-1,result,Ifisland);}return;
}
int main(){int n,m;cin>>n>>m;vector<vector<int>> graph(n,vector<int> (m));for(int i=0;i<n;i++){for(int j=0;j<m;j++){cin>>graph[i][j];}}int sumcount=0;vector<vector<bool>> finded(n,vector<bool> (m));for(int i=0;i<n;i++){for(int j=0;j<m;j++){if(graph[i][j]==1){bool Ifisland=true;int result=0;sum(finded,graph,i,j,result,Ifisland);if(Ifisland) sumcount+=result;} }}cout<<sumcount<<endl;    
}

102. 沉没孤岛//思路大致是，先遍历边框的，然后递归把连着的陆地都扫过，最后把没扫过的且为陆地的改为0。最后按题目的要求输出。

#include<bits/stdc++.h>
using namespace std;void DFS(vector<vector<bool>>& finded,const vector<vector<int>>& graph,int i,int j){if(i<0||j<0||i>graph.size()-1||j>graph[0].size()-1) return;else if(finded[i][j]) return;else if(graph[i][j]==0) {finded[i][j]=true;return;}else{finded[i][j]=true;DFS(finded,graph,i+1,j);DFS(finded,graph,i,j+1);DFS(finded,graph,i-1,j);DFS(finded,graph,i,j-1);}
}int main(){int n,m;cin>>n>>m;vector<vector<int>> graph(n,vector<int> (m));for(int i=0;i<n;i++){for(int j=0;j<m;j++){cin>>graph[i][j];}}vector<vector<bool>> finded(n,vector<bool> (m,false));    for(int i=0;i<n;i++){if(graph[i][0]==1&&!finded[i][0]) DFS(finded,graph,i,0);if(graph[i][m-1]==1&&!finded[i][m-1]) DFS(finded,graph,i,m-1);}  for(int j=0;j<m;j++){if(graph[0][j]==1&&!finded[0][j]) DFS(finded,graph,0,j);if(graph[n-1][j]==1&&!finded[n-1][j]) DFS(finded,graph,n-1,j);}for(int i=0;i<n;i++){for(int j=0;j<m;j++){if(graph[i][j]==1&&!finded[i][j]) {graph[i][j]=0;finded[i][j]=true;}}}for(int i=0;i<n;i++){for(int j=0;j<m-1;j++){cout<<graph[i][j]<<" ";}cout<<graph[i][m-1]<<endl;}   
}