H1. Maximize the Largest Component (Easy Version) - 题解

比赛与标签

比赛: Codeforces Round 952 (Div. 4) 标签: brute force, data structures, dfs and similar, dsu, graphs, implementation 难度: *1700

题目大意喵~

主人你好呀！这道题是这样的呐：

我们有一个 n 行 m 列的网格，里面有些格子是墙壁（#），有些是空地（.）。相邻（上下左右）的墙壁会连在一起，形成一个“连通块”。

我们有一个超能力！最多使用一次，我们可以选择任意一行或者任意一列，把里面的所有格子都变成墙壁（#）。

我们的任务就是，合理使用这次机会（或者不用），使得最终网格里最大的那个墙壁连通块，它的大小（也就是 # 的数量）最大。我们要输出这个最大值，喵~

简单来说，就是问：我们是填满某一行，还是填满某一列，还是什么都不做，才能得到最大的一个 # 덩어리 (clump) 呢？

本喵的解题思路！

这道题看起来要我们做出最优选择，那我们就把所有可能的选择都试一遍，然后取最好的结果就好啦！这种方法叫做枚举，的说。

总共有 n 行和 m 列可以选，所以我们有 n + m 种操作。当然，也包括什么都不做的选择。

但是，如果我们每次操作都真的去修改网格，然后再用 BFS/DFS 去找最大连通块，那也太慢了，肯定会超时的说！( TДT)

所以，我们需要一个更聪明的办法来快速计算每次操作后的结果！本喵的思路是这样的：

第一步：预处理，分析初始状态喵！

在做任何操作之前，网格里可能已经存在一些 # 连通块了。我们先用一次 BFS (广度优先搜索) 或者 DFS，把这些初始的连通块全都找出来。

对于每个连通块：

给它一个独一无二的 ID。
计算它的大小（包含多少个 #）。

我们可以用一个 comp_id[n][m] 的二维数组来记录每个 # 属于哪个连通块，再用一个 comp_size 数组来存每个连通块的大小。这样，我们就对整个棋盘的初始状态了如指掌啦！

同时，我们先计算一下什么都不做时的最大连通块大小，作为我们的初始答案 ans。

第二步：枚举操作，快速计算结果！

接下来，我们就要枚举填满每一行或每一列的情况了。

当填满第 r 行时： 所有在第 r 行的格子都变成了 #，它们会连成一条线。这个新形成的连通块的大小等于：

新增加的 # 数量：这正好是第 r 行原来是 . 的格子数量。我们可以提前把每行每列的 . 数量都统计好。
合并进来的旧连通块的大小之和：哪些旧连通块会被合并进来呢？就是那些“紧挨着”第 r 行的连通块。一个连通块只要有任何一个 # 在第 r-1 行、第 r 行或者第 r+1 行，它就会和我们新填的这一行连在一起！

所以，对于要填充的第 r 行，我们只需要遍历这一行相邻的所有格子（也就是 r-1, r, r+1 行的所有格子），找出它们所属的连通块 ID，然后把这些 不重复的 连通块的大小加起来。

注意！ 一个大的连通块可能在好几个地方都和第 r 行相邻，我们只能加一次它的大小哦！所以需要一个 seen_comp 数组来判重，确保每个连通块只被计算一次。

当填满第 c 列时： 逻辑和填满一行是完全一样的，只不过方向变了而已，喵~ 我们把和第 c 列相邻的（c-1, c, c+1 列）所有不重复的连通块的大小加起来，再加上第 c 列新增的 # 数量，就是填充这一列能得到的最大连通块大小啦。

最后一步： 我们枚举完所有 n 行和 m 列，每次都计算出一个潜在的最大值，并用它来更新我们的最终答案 ans。最后输出 ans 就大功告成啦！

这个方法通过一次预处理，把之后每次操作的计算量都降了下来，非常高效，的说！

代码实现时间到！

cpp

#include <iostream>
#include <vector>
#include <string>
#include <queue>
#include <algorithm>
#include <numeric>

void solve() {
    int n, m;
    std::cin >> n >> m;
    std::vector<std::string> grid(n);
    for (int i = 0; i < n; ++i) {
        std::cin >> grid[i];
    }

    // comp_id[i][j] 记录每个'#'格子所属的连通块ID，-1表示不是'#'或还没访问过
    std::vector<std::vector<int>> comp_id(n, std::vector<int>(m, -1));
    // comp_size 记录每个连通块的大小
    std::vector<int> comp_size;
    int comp_cnt = 0; // 连通块的计数器/ID

    // 用来做BFS的四个方向
    int dx[] = {0, 0, 1, -1};
    int dy[] = {1, -1, 0, 0};

    // 喵~ 预处理阶段！用BFS找出所有初始的'#'连通块
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < m; ++j) {
            if (grid[i][j] == '#' && comp_id[i][j] == -1) {
                std::queue<std::pair<int, int>> q;
                q.push({i, j});
                comp_id[i][j] = comp_cnt;
                int current_size = 1;
                while (!q.empty()) {
                    auto [r, c] = q.front();
                    q.pop();
                    for (int k = 0; k < 4; ++k) {
                        int nr = r + dx[k];
                        int nc = c + dy[k];
                        if (nr >= 0 && nr < n && nc >= 0 && nc < m &&
                            grid[nr][nc] == '#' && comp_id[nr][nc] == -1) {
                            comp_id[nr][nc] = comp_cnt;
                            current_size++;
                            q.push({nr, nc});
                        }
                    }
                }
                comp_size.push_back(current_size);
                comp_cnt++;
            }
        }
    }

    // 初始答案是“什么都不做”时的最大连通块大小
    int ans = 0;
    if (!comp_size.empty()) {
        ans = *std::max_element(comp_size.begin(), comp_size.end());
    }

    // 预计算每行每列有多少个'.'，也就是可以新增多少'#'
    std::vector<int> row_dots(n, 0);
    std::vector<int> col_dots(m, 0);
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < m; ++j) {
            if (grid[i][j] == '.') {
                row_dots[i]++;
                col_dots[j]++;
            }
        }
    }
    
    // 用来标记在单次计算中，哪些连通块已经被计算过了
    std::vector<bool> seen_comp(comp_cnt, false);

    // 枚举每一行
    for (int r = 0; r < n; ++r) {
        long long current_comp_sum = 0;
        std::vector<int> comps_to_reset; // 记录本次操作影响到的连通块，方便重置seen_comp
        // 遍历这一行的所有格子，检查相邻的连通块
        for (int j = 0; j < m; ++j) {
            // 检查 r-1, r, r+1 行的格子，看它们是否属于某个连通块
            for (int dr = -1; dr <= 1; ++dr) {
                int nr = r + dr;
                if (nr >= 0 && nr < n && grid[nr][j] == '#') {
                    int id = comp_id[nr][j];
                    if (!seen_comp[id]) { // 如果这个连通块还没被算过
                        seen_comp[id] = true;
                        current_comp_sum += comp_size[id];
                        comps_to_reset.push_back(id);
                    }
                }
            }
        }
        // 总大小 = 合并的旧连通块大小 + 新增的'#'数量
        ans = std::max(ans, (int)(current_comp_sum + row_dots[r]));
        // 重置标记，为下一次计算做准备喵
        for (int id : comps_to_reset) {
            seen_comp[id] = false;
        }
    }

    // 枚举每一列，逻辑同上
    for (int c = 0; c < m; ++c) {
        long long current_comp_sum = 0;
        std::vector<int> comps_to_reset;
        for (int i = 0; i < n; ++i) {
            for (int dc = -1; dc <= 1; ++dc) {
                int nc = c + dc;
                if (nc >= 0 && nc < m && grid[i][nc] == '#') {
                    int id = comp_id[i][nc];
                    if (!seen_comp[id]) {
                        seen_comp[id] = true;
                        current_comp_sum += comp_size[id];
                        comps_to_reset.push_back(id);
                    }
                }
            }
        }
        ans = std::max(ans, (int)(current_comp_sum + col_dots[c]));
        for (int id : comps_to_reset) {
            seen_comp[id] = false;
        }
    }

    std::cout << ans << "\n";
}

int main() {
    // 加速输入输出，是个好习惯喵~
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(NULL);
    int t;
    std::cin >> t;
    while (t--) {
        solve();
    }
    return 0;
}

这个算法快不快捏？

时间复杂度: O(N*M) 的说。
- 预处理找连通块的 BFS/DFS 会访问每个格子一次，所以是 O(N*M)。
- 统计每行每列的 . 数量也是 O(N*M)。
- 枚举所有行的操作：对于 n 行，每行我们都遍历 m 列，并做常数次邻居检查，总共是 O(N*M)。
- 枚举所有列的操作：同理，也是 O(N*M)。
- 把它们加起来，总的时间复杂度还是 O(N*M)。因为题目保证了所有测试用例的 N*M 总和不超过 10^6，所以这个速度是完全没问题的！
空间复杂度: O(N*M) 的说。
- 我们需要 grid 和 comp_id 两个二维数组，它们的大小都是 O(N*M)。
- BFS 的队列在最坏情况下也可能达到 O(N*M)。
- 所以空间复杂度主要由这些和网格大小相关的数组决定。

喵喵小课堂开课啦！

这道题真有趣，让本喵来总结一下学到了什么吧！

核心思想: 面对这种“枚举所有可能操作”的题目，一个关键的优化思路就是 预处理 + 快速计算。我们不是对每个操作都从头模拟，而是先花时间分析好初始局面（预处理），然后利用这些信息来快速地（通常是 O(1) 或接近 O(1)）推导出每个操作的结果。
图的遍历: 识别网格中的连通块是图论的基本功！BFS 和 DFS 都是非常强大的工具，一定要熟练掌握它们呐。
细节决定成败: 在计算合并后的连通块大小时，一定要记得去重！忘记去重会导致同一个连通块的大小被加好几次，答案就错啦。使用一个 seen 数组或者 std::set 是很好的去重方法。
对称性思考: 解决完“填满一行”的问题后，“填满一列”的问题其实是完全一样的，只是行列互换。在写代码时可以利用这种对称性，让思路更清晰。

总之，把一个复杂问题分解成“预处理”和“查询/计算”两个阶段，是解决很多算法题的法宝哦！主人要记住呀，下次遇到类似的题目，就可以从这个角度思考啦！加油喵~ (ฅ'ω'ฅ)

H1. Maximize the Largest Component (Easy Version) - 题解 ​

比赛与标签 ​

题目大意喵~ ​

本喵的解题思路！ ​

代码实现时间到！ ​

这个算法快不快捏？ ​

喵喵小课堂开课啦！ ​