Maximize the Largest Component 题解

本题的 Easy Version 题解

提示：

题解已在洛谷本题题解栏目展出，可选择进入洛谷查看此博客文章。
题目传送门：洛谷 / codeforces

题目大意

该题目要求在一个由 . 和 # 组成的网格中，通过选择某一行或某一列，将该行或该列所有字符设置为 #，使得整个网格中 # 组成的最大连通块的大小最大化。

题目给定了多个测试用例，每个测试用例包含一个 n\times m 的网格，网格中的每个字符是 . 或 #。要求我们找到执行一次操作后，# 组成的最大连通块的最大值。

解题思路

大致解题路线：

BFS 搜索连通块，并记录连通块编号和大小，以备后用。
n 行遍历找最大。
m 行遍历找最大。

整体思路简单，但是码量十足。。。

下面是更具体的思路。

初始化和输入处理：
- 首先读取输入的网格，并初始化访问标记数组 vis，该数组用于记录每个格子是否被访问过。
- 使用广度优先搜索 BFS 来计算原始网格中每个连通块的大小，并将这些大小记录在一个字典 tong 中。
模拟操作：
- 对于每一行，假设将整行设置为 #，计算由此形成的最大连通块。
- 对于每一列，假设将整列设置为 #，计算由此形成的最大连通块。
- 需要特别处理边界情况，确保相邻连通块不会因为重复计入而造成计算错误。
计算最大连通块：
- 遍历每一行和每一列，模拟将该行或该列设置为 # 后的连通块大小。
- 最后输出所有可能结果中的最大值。
具体操作请看下方代码。

代码实现

#include<bits/stdc++.h>
using namespace std;

const int N = 1005; // 网格的最大尺寸
int t, n, m; // t表示测试用例数量，n和m分别表示网格的行数和列数
int fx[5] = {0, 1, 0, -1, 0}; // BFS的方向数组，表示上下左右四个方向的行偏移量
int fy[5] = {0, 0, 1, 0, -1}; // BFS的方向数组，表示上下左右四个方向的列偏移量
int flag; // 连通块编号

queue<int> q1, q2; // BFS队列，分别存储行坐标和列坐标

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);

    cin >> t; // 读取测试用例数量
    while (t--) { 
        cin >> n >> m; // 读取当前网格的行数和列数
        vector<vector<char>> a(n + 2, vector<char>(m + 2)); // 定义网格，边界用于处理
        vector<vector<int>> vis(n + 2, vector<int>(m + 2, 0)); // 标记连通块编号
        flag = 0; // 连通块标记初始化
        map<int, int> tong; // 存储每个连通块的大小

        // 读取网格数据
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= m; j++) {
                cin >> a[i][j];
            }
        }

        // BFS计算连通块大小
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= m; j++) {
                if (vis[i][j] == 0 && a[i][j] == '#') { // 如果当前格子未被访问且是'#'
                    flag++; // 更新连通块编号
                    vis[i][j] = flag; // 标记当前连通块编号
                    q1.push(i);
                    q2.push(j);
                    tong[flag]++; // 初始化连通块大小

                    // BFS扩展连通块
                    while (!q1.empty()) {
                        int nx = q1.front();
                        int ny = q2.front();
                        q1.pop(); 
                        q2.pop(); 

                        for (int i = 1; i <= 4; i++) { // 遍历四个方向
                            int xx = nx + fx[i], yy = ny + fy[i];
                            if (a[xx][yy] == '#' && !vis[xx][yy] && xx <= n && yy <= m && xx >= 1 && yy >= 1) {
                                q1.push(xx);
                                q2.push(yy);
                                vis[xx][yy] = flag; // 标记相邻格子
                                tong[flag]++; // 增加连通块大小
                            }
                        }
                    }
                }
            }
        }

        int ans = 0; // 存储最大连通块大小
        map<int, int> vis2, biaoji; // 辅助标记

        // 处理每一行
        for (int i = 1; i <= n; i++) {
            int cnt = 0; // 当前行形成的连通块大小
            biaoji.clear(); 
            vis2.clear();
            for (int j = 1; j <= m; j++) {
                if (a[i][j] == '#') {
                    vis2[vis[i][j]] = 1; 
                }
                if (a[i][j] == '.') cnt++;
                else if (!biaoji[vis[i][j]]) { // 如果连通块未被标记
                    biaoji[vis[i][j]] = 1; // 标记当前连通块
                    cnt += tong[vis[i][j]]; // 累加连通块大小
                }
                if (!biaoji[vis[i - 1][j]] && a[i - 1][j] == '#' && vis[i - 1][j] != vis[i][j]) {
                    cnt += tong[vis[i - 1][j]]; // 累加上方连通块
                    biaoji[vis[i - 1][j]] = 1; 
                    if (vis2[vis[i - 1][j]] == 1) cnt--; // 避免重复计入
                }
                if (!biaoji[vis[i + 1][j]] && a[i + 1][j] == '#' && vis[i + 1][j] != vis[i][j]) {
                    cnt += tong[vis[i + 1][j]]; // 累加下方连通块
                    biaoji[vis[i + 1][j]] = 1; 
                    if (vis2[vis[i + 1][j]] == 1) cnt--; 
                }
            }
            ans = max(ans, cnt); // 更新最大连通块大小
        }

        // 处理每一列
        for (int j = 1; j <= m; j++) {
            int cnt = 0; // 当前列形成的连通块大小
            biaoji.clear(); 
            vis2.clear(); 
            for (int i = 1; i <= n; i++) {
                if (a[i][j] == '#') {
                    vis2[vis[i][j]] = 1; 
                }
                if (a[i][j] == '.') cnt++;
                else if (!biaoji[vis[i][j]]) { 
                    biaoji[vis[i][j]] = 1; 
                    cnt += tong[vis[i][j]]; 
                }
                if (!biaoji[vis[i][j - 1]] && a[i][j - 1] == '#' && vis[i][j - 1] != vis[i][j]) {
                    cnt += tong[vis[i][j - 1]]; // 累加左侧连通块
                    biaoji[vis[i][j - 1]] = 1; 
                    if (vis2[vis[i][j - 1]] == 1) cnt--; 
                }
                if (!biaoji[vis[i][j + 1]] && a[i][j + 1] == '#' && vis[i][j + 1] != vis[i][j]) {
                    cnt += tong[vis[i][j + 1]]; // 累加右侧连通块
                    biaoji[vis[i][j + 1]] = 1; 
                    if (vis2[vis[i][j + 1]] == 1) cnt--; 
                }
            }
            ans = max(ans, cnt); // 更新最大连通块大小
        }

        cout << ans << endl; // 输出最大连通块的大小
    }
    return 0;
}

复杂度分析

时间复杂度:
- 每个测试用例的时间复杂度主要分为两部分：BFS 用于找到所有的连通块，复杂度为 O(n \times m)，而行和列的遍历为 O(n \times m)。
- 因此总体时间复杂度为 O(t \times n \times m)，其中 t 是测试用例数。
空间复杂度:
- 额外使用了 vis 和 tong 两个数组，空间复杂度为 O(n \times m)。
喜欢的话不要忘记点赞哈！有任何疑问或见解欢迎在页面下方评论区发布！