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

101. 孤岛的总面积

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

DFS思路

思路:

代码结构

  1. 变量和方向数组:

    • dir[4][2]:定义了四个方向的移动(上、左、下、右)。
    • count:用于统计符合条件的陆地块数量。
  2. 深度优先搜索函数 dfs:

    • 输入参数为二维数组 grid 和当前坐标 (x, y)
    • 将当前坐标的值设为 0(表示已访问)。
    • 增加 count 计数。
    • 遍历四个方向,递归调用 dfs,前提是新坐标在边界内且值为 1(表示陆地)。
  3. 主函数 main:

    • 读取网格的大小 nm
    • 初始化一个 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思路

思路:

代码结构

  1. 方向数组 dir

    • 表示四个方向(右、下、左、上)的移动。
    • dir[4][2] = {0, 1, 1, 0, -1, 0, 0, -1} 表示:
      • 右:(0, 1)
      • 下:(1, 0)
      • 左:(-1, 0)
      • 上:(0, -1)
  2. 全局变量 count

    • 用于统计符合条件的陆地格子数量。
  3. 广度优先搜索函数 bfs

    • 参数:网格 grid,起始坐标 (x, y)
    • 使用队列 que 来实现BFS。
    • 将起始点标记为访问过(设置为0)并加入队列。
    • 遍历队列中的每个点,向四个方向扩展。
    • 检查边界条件,确保不越界。
    • 对于相邻的陆地格子,标记为访问过并加入队列。
  4. 主函数 main

    • 输入:网格大小 nm,以及网格数据。
    • 初始化网格 grid
    • 从网格的边界开始,移除与边界相连的陆地。
    • 重置 count
    • 遍历整个网格,统计被包围的陆地数量。
    • 输出结果。

逻辑流程

  1. 输入处理

    • 读取网格的大小 nm
    • 读取网格数据,填充 grid
  2. 边界BFS

    • 从网格的四个边界开始,使用 bfs 移除与边界相连的陆地。
    • 这部分陆地不计入最终统计,因为题目可能要求只统计被完全包围的陆地。
  3. 统计被包围的陆地

    • 重置 count
    • 遍历网格内部,使用 bfs 统计所有剩余陆地格子的数量。
  4. 输出结果

    • 打印出符合条件的陆地格子数量。

代码:

#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
题目状态:看题解

思路:

代码结构

  1. 方向数组 dir:

    • 定义了四个方向(上、左、下、右)的移动坐标:{-1, 0}{0, -1}{1, 0}{0, 1}
  2. DFS 函数:

    • 参数: 接受一个二维数组 grid 和当前坐标 (x, y)
    • 功能: 将当前陆地标记为 2,并递归遍历四个方向的相邻陆地。
    • 边界条件: 检查是否越界或遇到水(0)或已访问(2)的格子。
  3. 主函数 main:

    • 输入: 从标准输入读取网格大小 nm,以及网格数据。
    • 步骤一: 从边界开始,将与边界相连的陆地(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
题目状态:看题解

思路:

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

  1. 变量声明

    • n, m: 网格的行数和列数。
    • dir: 四个方向的移动向量,分别表示上、左、下、右。
  2. 函数 dfs

    • 参数:grid(网格)、visited(记录访问状态的二维布尔数组)、xy(当前坐标)。
    • 功能:从 (x, y) 开始,递归地访问所有可以到达的点。
    • 检查条件:
      • 如果当前点已经访问过,直接返回。
      • 确保下一个点在网格范围内。
      • 确保移动方向的高度不增加(即只能走向相等或更低的高度)。
  3. 函数 isResult

    • 参数:grid(网格)、xy(起始坐标)。
    • 功能:检查从 (x, y) 出发是否可以同时到达第一组和第二组边界。
    • 使用 dfs 标记从 (x, y) 可以到达的所有点。
    • 检查是否可以到达:
      • 第一组边界(上边界和左边界)。
      • 第二组边界(右边界和下边界)。
    • 返回 true 如果可以同时到达两组边界,否则返回 false
  4. main 函数

    • 读取网格的大小 nm
    • 读取网格的高度信息。
    • 遍历每个点 (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
题目状态:看题解,好难

思路:

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

  1. 变量声明

    • n, m: 网格的行数和列数。
    • count: 当前岛屿的面积。
    • dir: 四个方向的移动向量,分别表示右、下、左、上。
  2. 函数 dfs

    • 参数:grid(网格)、visited(记录访问状态的二维布尔数组)、xy(当前坐标)、mark(岛屿标记)。
    • 功能:通过深度优先搜索,将所有连接的陆地标记为同一个岛屿。
    • 终止条件:当前点已经访问过或是海水。
    • 标记当前陆地并递归访问相邻的陆地。
  3. main 函数

    • 读取网格的大小 nm
    • 读取网格的高度信息。
    • 初始化 visited 数组和 gridNum 映射,用于存储每个岛屿的面积。
    • 遍历网格,使用 dfs 查找并标记所有岛屿,记录每个岛屿的面积。
    • 检查是否整个网格都是陆地,如果是,直接输出总面积。
  4. 计算最大可能的岛屿面积

    • 遍历每个海水格子 (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;

}