【Day45 LeetCode】图论问题 Ⅲ

一、图论问题 Ⅲ

1、沉没孤岛

这题只能从边界开始扩散，将靠近边界的陆地标记，表示不是孤岛，最后将孤岛沉没，将不是孤岛标记回陆地。

# include<iostream>
# include<vector>

using namespace std;

void dfs(vector<vector<int>> &graph, int i, int j){
    if(i<0 || i>=graph.size() || j<0 || j>=graph[0].size() || graph[i][j]!=1)
        return;
    graph[i][j] = 2;
    dfs(graph, i+1, j);
    dfs(graph, i-1, j);
    dfs(graph, i, j+1);
    dfs(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];
    
    // 步骤一：
    // 从左侧边，和右侧边 向中间遍历
    for (int i = 0; i < n; i++) {
        if (graph[i][0] == 1) dfs(graph, i, 0);
        if (graph[i][m - 1] == 1) dfs(graph, i, m - 1);
    }

    // 从上边和下边 向中间遍历
    for (int j = 0; j < m; j++) {
        if (graph[0][j] == 1) dfs(graph, 0, j);
        if (graph[n - 1][j] == 1) dfs(graph, n - 1, j);
    }


    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            if (graph[i][j] == 1) graph[i][j] = 0;
            if (graph[i][j] == 2) graph[i][j] = 1;
        }
    }
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            cout << graph[i][j] << " ";
        }
        cout << endl;
    }
    return 0;
}

2、水流问题

如果想着从当前点向两个边界移动的话，时间复杂度过高，因为需要遍历每个点，每个点又需要扩散到两个边界。如果我们逆向思维，想着从边界出发去找可达的点，这一下就豁然开朗了。

# include<iostream>
# include<vector>

using namespace std;

vector<vector<int>> dirs = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
void dfs(vector<vector<int>> &graph, vector<vector<bool>> &vis,int ii, int jj){
    if(vis[ii][jj])
        return;
    vis[ii][jj] = true;
    for(auto xy : dirs){
        int i = ii + xy[0], j = jj + xy[1];
        if(i<0 || i>=graph.size() || j<0 || j>=graph[0].size() || graph[ii][jj] > graph[i][j] || vis[i][j])
            continue;
        dfs(graph, vis, i, j);
    }
}


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>> vis1(n, vector<bool>(m, false));
    vector<vector<bool>> vis2(n, vector<bool>(m, false)); 
    
    for(int i=0; i<n; ++i){
        dfs(graph, vis1, i, 0);
        dfs(graph, vis2, i, m-1);
    }
    for(int i=0; i<m; ++i){
        dfs(graph, vis1, 0, i);
        dfs(graph, vis2, n-1, i);
    }
    for(int i=0; i<n; ++i){
        for(int j=0; j<m; ++j){
            if(vis1[i][j] && vis2[i][j])
                cout << i << " " << j << endl;
        }
    }
    return 0;
}

3、建造最大岛屿

写了个很不优雅的代码，思路是 DFS遍历陆地，给每个岛屿一一对应的编号，并用哈希表记录编号与岛屿面积的对应关系。然后，第二次遍历图，遇到水域，遍历水域的四个方向上的编号，进行面积累加，一个细节是需要用set进行去重，可能四个反向上存在编号相同的区域。

# include<iostream>
# include<vector>
# include<unordered_map>
# include<unordered_set>
using namespace std;

int dfs(vector<vector<int>> &graph, int i, int j, int num){
    if(i<0 || i>=graph.size() || j<0 || j>=graph[0].size() || graph[i][j]!=1)
        return 0;
    graph[i][j] = num;
    return 1 + dfs(graph, i+1, j, num)+ dfs(graph, i-1, j, num)+ dfs(graph, i, j+1, num)+ dfs(graph, i, j-1, num);
} 

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];
    unordered_map<int, int> mp; // 映射几号陆地 与 其面积关系
    mp[0] = 0;
    int idx = 2; // 几号陆地 
    int ans = 0;
    for(int i=0; i<n; ++i){
        for(int j=0; j<m; ++j){
            if(graph[i][j]==1){
                mp[idx] = dfs(graph, i, j, idx);
                ans = max(ans, mp[idx]);
                ++idx;
            }
        }
    }
    vector<vector<int>> dirs = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
    for(int i=0; i<n; ++i){
        for(int j=0; j<m; ++j){
            if(graph[i][j]==0){
                int tmp = 1;
                unordered_set<int> set;
                for(auto xy : dirs){
                    int x = i + xy[0], y = j + xy[1];
                    if(x>=0 && x<n && y>=0 && y<m && set.find(graph[x][y])==set.end()){
                        set.insert(graph[x][y]);
                        tmp += mp[graph[x][y]];
                    }
                }
                ans = max(ans, tmp);
            }
        }
    }
    cout << ans << endl;
    
    return 0;
}