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;}

?

?