代码随想录算法训练营第五十二天|图论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;

}