「代码随想录算法训练营」第四十五天 | 图论 part3

2024-08-23 23:43 由云雀AC了一整天发表于 #其他

101. 孤岛的总面积
- DFS思路
- BFS思路
102. 沉没孤岛
103. 水流问题
104. 建造最大岛屿

101. 孤岛的总面积

题目链接：https://kamacoder.com/problempage.php?pid=1173
文章讲解：https://programmercarl.com/kamacoder/0101.孤岛的总面积.html
题目状态：看题解

DFS思路

思路：

代码结构

变量和方向数组:
- dir[4][2]：定义了四个方向的移动（上、左、下、右）。
- count：用于统计符合条件的陆地块数量。
深度优先搜索函数 dfs:
- 输入参数为二维数组 grid 和当前坐标 (x, y)。
- 将当前坐标的值设为 0（表示已访问）。
- 增加 count 计数。
- 遍历四个方向，递归调用 dfs，前提是新坐标在边界内且值为 1（表示陆地）。
主函数 main:
- 读取网格的大小 n 和 m。
- 初始化一个 n x m 的二维数组 grid。
- 从输入读取网格数据。
- 从网格的四个边界开始，使用 dfs 清除边界连接的陆地。
- 重置 count。
- 遍历内部陆地，使用 dfs 统计不与边界相连的陆地块。
- 输出 count。

逻辑分析

边界处理:
- 先从网格的边界开始，使用 dfs 清除与边界相连的陆地。这样可以排除掉与边界相连的陆地块。
统计孤立陆地:
- 遍历整个网格，使用 dfs 统计不与边界相连的陆地块。

代码：

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

int dir[4][2] = {-1, 0, 0, -1, 1, 0, 0, 1}; // 保存四个方向
int count; // 统计符合题目要求的陆地空格数量

void dfs(vector<vector<int>> &grid, int x, int y) {
    grid[x][y] = 0;
    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;
        // 不符合条件，不继续遍历
        if(grid[nextx][nexty] == 0) continue;

        dfs(grid, nextx,nexty);
    }
    return;
}

int main() {
    int n, m;
    cin >> n >> m;
    vector<vector<int>> grid(n, vector<int>(m, 0));
    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, i, 0);
        if(grid[i][m - 1] == 1) dfs(grid, i, m - 1);
    }

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

    count = 0;
    for(int i = 0; i < n; ++i) {
        for(int j = 0; j < m; ++j) {
            if(grid[i][j] == 1) dfs(grid, i, j);
        }
    }
    cout << count << endl;
}

BFS思路

思路：

代码结构

方向数组 dir：
- 表示四个方向（右、下、左、上）的移动。
- dir[4][2] = {0, 1, 1, 0, -1, 0, 0, -1} 表示：
  - 右：(0, 1)
  - 下：(1, 0)
  - 左：(-1, 0)
  - 上：(0, -1)
全局变量 count：
- 用于统计符合条件的陆地格子数量。
广度优先搜索函数 bfs：
- 参数：网格 grid，起始坐标 (x, y)。
- 使用队列 que 来实现BFS。
- 将起始点标记为访问过（设置为0）并加入队列。
- 遍历队列中的每个点，向四个方向扩展。
- 检查边界条件，确保不越界。
- 对于相邻的陆地格子，标记为访问过并加入队列。
主函数 main：
- 输入：网格大小 n 和 m，以及网格数据。
- 初始化网格 grid。
- 从网格的边界开始，移除与边界相连的陆地。
- 重置 count。
- 遍历整个网格，统计被包围的陆地数量。
- 输出结果。

逻辑流程

输入处理：
- 读取网格的大小 n 和 m。
- 读取网格数据，填充 grid。
边界BFS：
- 从网格的四个边界开始，使用 bfs 移除与边界相连的陆地。
- 这部分陆地不计入最终统计，因为题目可能要求只统计被完全包围的陆地。
统计被包围的陆地：
- 重置 count。
- 遍历网格内部，使用 bfs 统计所有剩余陆地格子的数量。
输出结果：
- 打印出符合条件的陆地格子数量。

代码：

#include <iostream>
#include <vector>
#include <queue>
using namespace std;

int dir[4][2] = {0, 1, 1, 0, -1, 0, 0, -1}; // 保存四个方向
int count = 0; // 统计符合题目要求的陆地空格数量

void bfs(vector<vector<int>> &grid, int x, int y) {
    queue<pair<int, int>> que;
    que.push({x, y});
    grid[x][y] = 0; // 只要加入队列，立即标记
    count++;
    while(!que.empty()) {
        pair<int, int> cur = que.front();
        que.pop();
        int curx = cur.first;
        int cury = cur.second;
        for(int i = 0; i < 4; ++i) {
            int nextx = curx + dir[i][0];
            int nexty = cury + dir[i][1];
            if(nextx < 0 || nextx >= grid.size() || nexty < 0 || nexty >= grid.size()) continue; // 越界了，直接跳过
            if(grid[nextx][nexty] == 1) {
                que.push({nextx, nexty});
                count++;
                grid[nextx][nexty] = 0; // 只要加入队列立刻标记
            }
        }
    }    
}

int main() {
    int n, m;
    cin >> n >> m;
    vector<vector<int>> grid(n, vector<int>(m, 0));
    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) bfs(grid, i, 0);
        if(grid[i][m - 1] == 1) bfs(grid, i, m - 1);
    }

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

    count = 0;
    for(int i = 0; i < n; ++i) {
        for(int j = 0; j < m; ++j) {
            if(grid[i][j] == 1) bfs(grid, i, j);
        }
    }
    cout << count << endl;
}

102. 沉没孤岛

题目链接：https://kamacoder.com/problempage.php?pid=1174
文章讲解：https://programmercarl.com/kamacoder/0102.沉没孤岛.html
题目状态：看题解

思路：

代码结构

方向数组 dir:
- 定义了四个方向（上、左、下、右）的移动坐标：{-1, 0}、{0, -1}、{1, 0}、{0, 1}。
DFS 函数:
- 参数: 接受一个二维数组 grid 和当前坐标 (x, y)。
- 功能: 将当前陆地标记为 2，并递归遍历四个方向的相邻陆地。
- 边界条件: 检查是否越界或遇到水（0）或已访问（2）的格子。
主函数 main:
- 输入: 从标准输入读取网格大小 n 和 m，以及网格数据。
- 步骤一: 从边界开始，将与边界相连的陆地（1）通过 DFS 标记为 2。
- 步骤二: 将剩余的陆地（孤岛）变成水（0）。
- 步骤三: 将标记为 2 的边界陆地恢复为陆地（1）。
- 输出: 打印修改后的网格。

逻辑流程

边界处理:
- 从网格的四条边界开始，使用 DFS 将所有与边界相连的陆地标记为 2。
孤岛处理:
- 遍历整个网格，将所有未标记为 2 的陆地（即孤岛）变为水（0）。
恢复边界陆地:
- 将标记为 2 的格子恢复为陆地（1），因为它们与边界相连。

代码：

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

int dir[4][2] = {-1, 0, 0, -1, 1, 0, 0, 1}; // 保存四个方向
void dfs(vector<vector<int>> &grid, int x, int y) {
    grid[x][y] = 2;
    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[nextx][nexty] == 0 || grid[nextx][nexty] == 2) continue;
        dfs(grid, nextx, nexty);
    }
    return;
}

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

    // 步骤一：（将边界陆地1变为2）
    // 从左边和右边向中间遍历
    for(int i = 0; i < n; ++i) {
        if(grid[i][0] == 1) dfs(grid, i, 0);
        if(grid[i][m - 1] == 1) dfs(grid, i, m - 1);
    }

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

    // 步骤二：将地图中的1（孤岛）变为0
    // 步骤三：将地图中的2（边界陆地）变为1
    for(int i = 0; i < n; ++i) {
        for(int j = 0; j < m; ++j) {
            if(grid[i][j] == 1) grid[i][j] = 0;
            if(grid[i][j] == 2) grid[i][j] = 1;
        }
    }

    for(int i = 0; i < n; ++i) {
        for(int j = 0; j < m; ++j) {
            cout << grid[i][j] << " ";
        }
        cout << endl;
    }
}

103. 水流问题

题目链接：https://kamacoder.com/problempage.php?pid=1175
文章讲解：https://programmercarl.com/kamacoder/0103.水流问题.html
题目状态：看题解

思路：

通过便利在给定的网格中找到能够同时到达两组边界的点。通过深度优先搜索，计算每个点可以访问的区域，并检查这些区域是否满足到达边界的条件。

变量声明
- n, m: 网格的行数和列数。
- dir: 四个方向的移动向量，分别表示上、左、下、右。
函数 dfs
- 参数：grid（网格）、visited（记录访问状态的二维布尔数组）、x、y（当前坐标）。
- 功能：从 (x, y) 开始，递归地访问所有可以到达的点。
- 检查条件：
  - 如果当前点已经访问过，直接返回。
  - 确保下一个点在网格范围内。
  - 确保移动方向的高度不增加（即只能走向相等或更低的高度）。
函数 isResult
- 参数：grid（网格）、x、y（起始坐标）。
- 功能：检查从 (x, y) 出发是否可以同时到达第一组和第二组边界。
- 使用 dfs 标记从 (x, y) 可以到达的所有点。
- 检查是否可以到达：
  - 第一组边界（上边界和左边界）。
  - 第二组边界（右边界和下边界）。
- 返回 true 如果可以同时到达两组边界，否则返回 false。
main 函数
- 读取网格的大小 n 和 m。
- 读取网格的高度信息。
- 遍历每个点 (i, j)，调用 isResult 检查是否满足条件。
- 如果满足条件，输出该点的坐标。

代码：

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

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

// 从x，y出发把可以走的地方都标记上
void dfs(vector<vector<int>> &grid, vector<vector<bool>> &visited, int x, int y) {
    if(visited[x][y]) return;
    visited[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 >= n || nexty < 0 || nexty >= m) continue;
        if(grid[x][y] < grid[nextx][nexty]) continue; // 高度不合适
        dfs(grid, visited, nextx, nexty);
    }
    return;
}

bool isResult(vector<vector<int>> &grid, int x, int y) {
    vector<vector<bool>> visited(n, vector<bool>(m, false));
    // 深搜，将x，y出发能到的节点都标记上
    dfs(grid, visited, x, y);
    bool isFirst = false;
    bool isSecond = false;
    // 以下就是判断x，y出发，是否到达第一组边界和第二组边界
    // 第一边界的上边
    for(int j = 0; j < m; ++j) {
        if(visited[0][j]) {
            isFirst = true;
            break;
        }
    }
    // 第一边界的左边
    for(int i = 0; i < n; ++i) {
        if(visited[i][0]) {
            isFirst = true;
            break;
        }
    }
    // 第二边界的右边
    for(int j = 0; j < m; ++j) {
        if(visited[n - 1][j]) {
            isSecond = true;
            break;
        }
    }
    // 第二边界下边
    for(int i = 0; i < n; ++i) {
        if(visited[i][m - 1]) {
            isSecond = true;
            break;
        }
    }
    if(isFirst && isSecond) return true;
    return false;
}

int main() {
    cin >> n >> m;
    vector<vector<int>> grid(n, vector<int>(m, 0));
    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) {
        for(int j = 0; j < m; ++j) {
            if(isResult(grid, i, j)) cout << i << " " << j << endl;
        }
    }
}

上述代码和思路在卡码网中运行会出现超时情况，下面是优化的思路和代码。

思路：

不进行单个元素的遍历，而是从边界向中间遍历。

代码：

#include <iostream>
#include <vector>
using namespace std;
int n, m;
int dir[4][2] = {-1, 0, 0, -1, 1, 0, 0, 1};
void dfs(vector<vector<int>>& grid, vector<vector<bool>>& visited, int x, int y) {
    if (visited[x][y]) return;

    visited[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 >= n || nexty < 0 || nexty >= m) continue;
        if (grid[x][y] > grid[nextx][nexty]) continue; // 注意：这里是从低向高遍历

        dfs (grid, visited, nextx, nexty);
    }
    return;
}

int main() {

    cin >> n >> m;
    vector<vector<int>> grid(n, vector<int>(m, 0));

    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            cin >> grid[i][j];
        }
    }
    // 标记从第一组边界上的节点出发，可以遍历的节点
    vector<vector<bool>> firstBorder(n, vector<bool>(m, false));

    // 标记从第一组边界上的节点出发，可以遍历的节点
    vector<vector<bool>> secondBorder(n, vector<bool>(m, false));

    // 从最上和最下行的节点出发，向高处遍历
    for (int i = 0; i < n; i++) {
        dfs (grid, firstBorder, i, 0); // 遍历最左列，接触第一组边界
        dfs (grid, secondBorder, i, m - 1); // 遍历最右列，接触第二组边界
    }

    // 从最左和最右列的节点出发，向高处遍历
    for (int j = 0; j < m; j++) {
        dfs (grid, firstBorder, 0, j); // 遍历最上行，接触第一组边界
        dfs (grid, secondBorder, n - 1, j); // 遍历最下行，接触第二组边界
    }
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            // 如果这个节点，从第一组边界和第二组边界出发都遍历过，就是结果
            if (firstBorder[i][j] && secondBorder[i][j]) cout << i << " " << j << endl;;
        }
    }
}

104. 建造最大岛屿

题目链接：https://kamacoder.com/problempage.php?pid=1176
文章讲解：https://programmercarl.com/kamacoder/0104.建造最大岛屿.html
题目状态：看题解，好难

思路：

找出通过将一个海水格子变为陆地后，可能形成的最大岛屿面积。通过标记和记录每个岛屿的面积，高效地计算出将某个海水格子变为陆地后的最大可能面积。

变量声明
- n, m: 网格的行数和列数。
- count: 当前岛屿的面积。
- dir: 四个方向的移动向量，分别表示右、下、左、上。
函数 dfs
- 参数：grid（网格）、visited（记录访问状态的二维布尔数组）、x、y（当前坐标）、mark（岛屿标记）。
- 功能：通过深度优先搜索，将所有连接的陆地标记为同一个岛屿。
- 终止条件：当前点已经访问过或是海水。
- 标记当前陆地并递归访问相邻的陆地。
main 函数
- 读取网格的大小 n 和 m。
- 读取网格的高度信息。
- 初始化 visited 数组和 gridNum 映射，用于存储每个岛屿的面积。
- 遍历网格，使用 dfs 查找并标记所有岛屿，记录每个岛屿的面积。
- 检查是否整个网格都是陆地，如果是，直接输出总面积。
计算最大可能的岛屿面积
- 遍历每个海水格子 (i, j)，尝试将其变为陆地。
- 对于每个海水格子，检查其四个相邻格子。
- 计算相邻岛屿的总面积（避免重复计算同一岛屿）。
- 更新最大岛屿面积。

代码：

#include <iostream>
#include <vector>
#include <unordered_set>
#include <unordered_map>
using namespace std;
int n, m;
int count;

int dir[4][2] = {0, 1, 1, 0, -1, 0, 0, -1}; // 四个方向
void dfs(vector<vector<int>>& grid, vector<vector<bool>>& visited, int x, int y, int mark) {
    if (visited[x][y] || grid[x][y] == 0) return; // 终止条件：访问过的节点 或者 遇到海水
    visited[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 >= n || nexty < 0 || nexty >= m) continue;  // 越界了，直接跳过
        dfs(grid, visited, nextx, nexty, mark);
    }
}

int main() {
    cin >> n >> m;
    vector<vector<int>> grid(n, vector<int>(m, 0));

    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            cin >> grid[i][j];
        }
    }
    vector<vector<bool>> visited(n, vector<bool>(m, false)); // 标记访问过的点
    unordered_map<int ,int> gridNum;
    int mark = 2; // 记录每个岛屿的编号
    bool isAllGrid = true; // 标记是否整个地图都是陆地
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            if (grid[i][j] == 0) isAllGrid = false;
            if (!visited[i][j] && grid[i][j] == 1) {
                count = 0;
                dfs(grid, visited, i, j, mark); // 将与其链接的陆地都标记上 true
                gridNum[mark] = count; // 记录每一个岛屿的面积
                mark++; // 记录下一个岛屿编号
            }
        }
    }
    if (isAllGrid) {
        cout << n * m << endl; // 如果都是陆地，返回全面积
        return 0; // 结束程序
    }

    // 以下逻辑是根据添加陆地的位置，计算周边岛屿面积之和
    int result = 0; // 记录最后结果
    unordered_set<int> visitedGrid; // 标记访问过的岛屿
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            count = 1; // 记录连接之后的岛屿数量
            visitedGrid.clear(); // 每次使用时，清空
            if (grid[i][j] == 0) {
                for (int k = 0; k < 4; k++) {
                    int neari = i + dir[k][1]; // 计算相邻坐标
                    int nearj = j + dir[k][0];
                    if (neari < 0 || neari >= n || nearj < 0 || nearj >= m) continue;
                    if (visitedGrid.count(grid[neari][nearj])) continue; // 添加过的岛屿不要重复添加
                    // 把相邻四面的岛屿数量加起来
                    count += gridNum[grid[neari][nearj]];
                    visitedGrid.insert(grid[neari][nearj]); // 标记该岛屿已经添加过
                }
            }
            result = max(result, count);
        }
    }
    cout << result << endl;

}