代码随想录算法训练营 Day52 图论Ⅲ 岛屿问题Ⅱ 面积 孤岛 水流 造岛

图论

题目

101. 孤岛的总面积
计算孤岛总面积，一个想法是将相邻的陆地的位置置为 0，最后计算孤岛面积中最小的一个

#include <iostream>
#include <vector>
#include <queue>

using namespace std;

int sum = 0;
int dir[4][2] = {0,-1,-1,0,0,1,1,0};

// 这里面的vis没用到写出来就是联系模板代码用的
void dfs(vector<vector<int>>& grid, vector<vector<bool>>& vis, int x, int y) {
    if (vis[x][y] || grid[x][y] == 0) return;
    grid[x][y] = 0;
    vis[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 >= grid.size() || nextY < 0 || nextY >= grid[0].size()) continue;
        dfs(grid, vis, nextX, nextY);
    }
}

void bfs(vector<vector<int>>& grid, vector<vector<bool>>& vis, int x, int y) {
    queue<pair<int, int>> que;
    que.push(make_pair(x, y));
    vis[x][y] = true;
    grid[x][y] = 0;
    while (!que.empty()) {
        pair<int, int> cur = que.front();
        que.pop();
        for (int i = 0; i < 4; ++i) {
            int nextX = cur.first + dir[i][0];
            int nextY = cur.second + dir[i][1];
            if (nextX < 0 || nextX >= grid.size() || nextY < 0 || nextY >= grid[0].size()) continue;
            if (grid[nextX][nextY] == 1 && !vis[nextX][nextY]) {
                grid[nextX][nextY] = 0;
                vis[nextX][nextY] = true;
                que.push({nextX, nextY});
            }
        }
    }
}

int main() {
    int n, m;
    cin >> n >> m;
    vector<vector<int>> grid(n, vector<int>(m, 0));
    vector<vector<bool>> vis(n, vector<bool>(m, false));
    for (int i = 0; i < n; ++i) { 
        for (int j = 0; j < m; ++j ){
            cin >> grid[i][j];
        }
    }

    // 将紧邻陆置为0
    for (int i = 0; i < n; ++i) {
        if (grid[i][0] == 1) dfs(grid, vis, i, 0);
        if (grid[i][m-1] == 1) dfs(grid, vis, i, m-1);
    }
    for (int j = 0; j < m; ++j) {
        if (grid[0][j] == 1) bfs(grid, vis, 0, j);
        if (grid[n-1][j] == 1) bfs(grid, vis, n-1, j);
    }

    // 遍历孤岛总面积
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < m; ++j) {
            if (grid[i][j] == 1) sum++;
        }
    }

    cout << sum << endl;
}

102. 沉没孤岛
沉默孤岛就可以使用 vis 数组了，遍历大陆框架
For (int i = 0; i < n; ++i) 这样从边框遍历，并记录遍历结果，最后 vis 就是我们访问过的非孤岛
返回 vis 就是将孤岛沉没后的结果

#include <iostream>
#include <vector>
#include <queue>

using namespace std;

int dir[4][2] = {0,-1,-1,0,0,1,1,0};
void dfs(vector<vector<int>>& grid, vector<vector<bool>>& vis, int x, int y) {
    vis[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 >= grid.size() || nextY < 0 || nextY >= grid[0].size()) continue;
        if (!vis[nextX][nextY] && grid[nextX][nextY] == 1) {
            dfs(grid, vis, nextX, nextY);
        }
    }
}

void bfs(vector<vector<int>>& grid, vector<vector<bool>>& vis, int x, int y) {
    queue<pair<int, int>> que;
    que.push(make_pair(x, y));
    vis[x][y] = true;
    while (!que.empty()) {
        pair<int, int> cur = que.front();
        que.pop();
        for (int i = 0; i < 4; ++i) {
            int nextX = cur.first + dir[i][0];
            int nextY = cur.second + dir[i][1];
            if (nextX < 0 || nextX >= grid.size() || nextY < 0 || nextY >= grid[0].size()) continue;
            if (!vis[nextX][nextY] && grid[nextX][nextY] == 1) {
                vis[nextX][nextY] = true;
                que.push({nextX, nextY});
            }
        } 
    }
}

int main() {
    int n, m;
    cin >> n >> m;
    vector<vector<int>> grid(n, vector<int>(m, 0));
    vector<vector<bool>> vis(n, vector<bool>(m, false));
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < m; ++j) {
            cin >> grid[i][j];
        }
    }
    
    for (int i = 0; i < n; ++i) {
        if (grid[i][0] == 1) dfs(grid, vis, i, 0);
        if (grid[i][m-1] == 1) dfs(grid, vis, i, m-1);
    }
    
    for (int j = 0; j < m; ++j) {
        if (grid[0][j] == 1) bfs(grid, vis, 0, j);
        if (grid[n-1][j] == 1) bfs(grid, vis, n-1, j);
    }
    
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < m-1; ++j) {
            cout << vis[i][j] << " ";
        }
        cout << vis[i][m-1] << endl;
    }
}

103. 水流问题
题目是问：有没有一个节点可以让水流流到第一边界与第二边界，如果有输出这个节点的坐标
暴力想法：遍历每一个节点查看是否可以从该节点遍历到第一边界与第二边界
这样可以实现，但是时间复杂度太高，因为要对每个节点遍历整张地图
逆向想法：从第一边界与第二边界边开始逆向遍历
这样就只用遍历四个边的内容而不用遍历到里面的内容，减少了计算量
而且实际代码中流水是一条路径，遍历当前边的其他节点遇见了之前的路径就可以跳过了
Dfs bfs 判断条件就是要大于等于当前值的才继续搜索，从而实现标记
最后通过比较两个 vis 数组都 true的节点输出坐标即可
最后本质上由于 vis 存在每个节点至多访问一次复杂度为 n * m

#include <iostream>
#include <vector>
#include <queue>

using namespace std;

int dir[4][2] = {0,-1,-1,0,0,1,1,0};

void dfs(vector<vector<int>>& grid, vector<vector<bool>>& vis, int x, int y) {
    // 终止条件访问过了就退出
    if (vis[x][y]) return;
    vis[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 >= grid.size() || nextY < 0 || nextY >= grid[0].size()) continue;
        // 水流情况判断 逆向蔓延往高处流
        if (grid[x][y] > grid[nextX][nextY]) continue;
        dfs(grid, vis, nextX, nextY);
    }
    return;
}

void bfs(vector<vector<int>>& grid, vector<vector<bool>>& vis, int x, int y) {
    queue<pair<int, int>> que;
    que.push(make_pair(x, y));
    vis[x][y] = true;
    while (!que.empty()) {
        pair<int, int> cur = que.front();
        que.pop();
        for (int i = 0; i < 4; ++i) {
            int nextX = cur.first + dir[i][0];
            int nextY = cur.second + dir[i][1];
            if (nextX < 0 || nextX >= grid.size() || nextY < 0 || nextY >= grid[0].size()) continue;
            // 水流方向判断
            if (grid[cur.first][cur.second] > grid[nextX][nextY]) continue;
            if (!vis[nextX][nextY]){
                vis[nextX][nextY] = true;
                que.push(make_pair(nextX, nextY));
            }
        }
    }
}

int main() {
    int n, m;
    cin >> n >> m;
    vector<vector<int>> grid(n, vector<int>(m, 0));
    vector<vector<bool>> firstVis(n, vector<bool>(m, false));
    vector<vector<bool>> secondVis(n, vector<bool>(m, false));
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < m; ++j) {
            cin >> grid[i][j];
        }
    }

    // 从两边逆向遍历
    for (int i = 0; i < n; ++i) {
        dfs(grid, firstVis, i, 0);
        dfs(grid, secondVis, i, m-1);
    }

    for (int j = 0; j < m; ++j) {
        bfs(grid, firstVis, 0, j);
        bfs(grid, secondVis, n-1, j);
    }

    // 输出结果 只有两个vis均为true的时候输出坐标
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < m; ++j) {
            if (firstVis[i][j] && secondVis[i][j]) {
                cout << i << " " << j << endl;
            }
        }
    }
    return 0;
}

104. 建造最大岛屿
建造岛屿问题，默认方法就是遍历
优化方法：由于给出的是岛屿地图因此可以对不同岛屿编号直接利用岛屿编号代替遍历
1. 对岛屿遍历记录岛屿的编号与面积的关系，使用 unordermap
2. 对地图中每个海洋 0 变成 1 后直接遍历周围遍历到岛屿的时候直接取编号相加即可
这里面要防止重复添加可以记录已经添加了的岛屿到集合中搜索到之后就不再添加了

#include <iostream>
#include <vector>
#include <queue>
#include <unordered_map>
#include <unordered_set>

using namespace std;

int markIdx = 1, count = 0;
int dir[4][2] = {0,-1,-1,0,0,1,1,0};

void dfs(vector<vector<int>>& grid, vector<vector<bool>>& vis, int x, int y, int mark) {
    if (vis[x][y] || grid[x][y] == 0) return;
    vis[x][y] = true;
    grid[x][y] = mark;
    count++; // 统计当前岛屿的面积
    for (int i = 0; i < 4; ++i) {
        int nextX = x + dir[i][0];
        int nextY = y + dir[i][1];
        if (nextX < 0 || nextX >= grid.size() || nextY < 0 || nextY >= grid[0].size()) continue;
        dfs(grid, vis, nextX, nextY, mark);
    }
}

int main() {
    int n, m, res = 0;
    cin >> n >> m;
    unordered_map<int, int> map; // 记录岛屿编号与岛屿面积
    unordered_set<int> set; // 记录参与计算面积的岛屿
    vector<vector<int>> grid(n, vector<int>(m, 0));
    vector<vector<bool>> vis(n, vector<bool>(m, false));
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < m; ++j) {
            cin >> grid[i][j];
        }
    }

    bool allLand = true;
    // 步骤一 遍历岛屿记录岛屿面积与标号 mark从2开始 1表示填海造陆的岛屿
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < m; ++j) {
            if (grid[i][j] == 0) allLand = false;
            if (!vis[i][j] && grid[i][j] == 1) {
                count = 0;
                markIdx = markIdx+1;
                dfs(grid, vis, i, j, markIdx);
                map[markIdx] = count;
            }
        }
    }

    if(allLand) {
        cout << n * m << endl;
        return 0;
    }

    // 步骤二 遍历整个地图将海洋变成岛屿 然后遍历岛屿记录面积
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < m; ++j) {
            count = 1; // 海洋变成了陆地用于记录陆地面积
            set.clear(); // 清空选择
            if (grid[i][j] == 0) {
                for (int k = 0; k < 4; ++k){
                    int nextX = i + dir[k][0];
                    int nextY = j + dir[k][1];
                    if (nextX < 0 || nextX >= grid.size() || nextY < 0 || nextY >= grid[0].size()) continue;
                    // 记录是否添加了这个岛屿
                    if (set.count(grid[nextX][nextY])) continue;
                    count += map[grid[nextX][nextY]];
                    set.insert(grid[nextX][nextY]);
                }
            }
            res = max(res, count);
        }
    }

    cout << res << endl;
}

// 模式2

#include <iostream>
#include <vector>
#include <queue>
#include <unordered_set>
#include <unordered_map>

using namespace std;

int count = 0;
int dir[4][2] = {0,-1,-1,0,0,1,1,0};

void bfs(vector<vector<int>>& grid, vector<vector<bool>>& vis, int x, int y, int mark) {
    queue<pair<int, int>> que;
    que.push({x, y});
    vis[x][y] = true;
    grid[x][y] = mark;
    while (!que.empty()) {
        pair<int, int> cur = que.front();
        que.pop();
        for (int i = 0; i < 4; ++i) {
            int nextX = cur.first + dir[i][0];
            int nextY = cur.second + dir[i][1];
            if (nextX < 0 || nextX >= grid.size() || nextY < 0 || nextY >= grid[0].size()) continue;
            if (!vis[nextX][nextY] && grid[nextX][nextY] == 1) {
                que.push({nextX, nextY});
                vis[nextX][nextY] = true;
                grid[nextX][nextY] = mark;
                count++;
            }
        }
    }
}

int main() {
    int n,m, markIdx = 2, sum = 0;
    cin >> n >> m;
    vector<vector<int>> grid(n, vector<int>(m, 0));
    vector<vector<bool>> vis(n, vector<bool>(m, false));
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < m; ++j) {
            cin >> grid[i][j];
        }
    }

    bool allLand = true;
    unordered_map<int, int> map;
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < m; ++j) {
            if (grid[i][j] == 0) allLand = false;
            if (!vis[i][j] && grid[i][j] == 1) {
                count = 1;
                bfs(grid, vis, i, j, markIdx);
                map[markIdx] = count;
                markIdx++;
            }
        }
    }
    if (allLand) {
        cout << n * m << endl;
        return 0;
    }

    unordered_set<int> set;
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < m; ++j) {
            count = 0;
            set.clear();
            if (grid[i][j] == 0) {
                count = 1;
                for (int k = 0; k < 4; ++k) {
                    int nextX = i + dir[k][0];
                    int nextY = j + dir[k][1];
                    if (nextX < 0 || nextX >= grid.size() || nextY < 0 || nextY >= grid[0].size()) continue;
                    if (set.count(grid[nextX][nextY])) continue;
                    count += map[grid[nextX][nextY]];
                    set.insert(grid[nextX][nextY]);
                }
            }
            sum = max(sum, count);
        }
    }

    cout << sum << endl;
    return 0;
}