H1. Maximize the Largest Component (Easy Version)

题目链接：Problem - H1 - Codeforces

题目大意：给一个由‘.' 与’#‘的字符组合成的二维矩阵，现在又有一种操作可以使每一列或每一行全部变成’#‘，然后求这个二维矩阵里的由’#‘组合成的最大连通块，求出该最大连通块的大小。

输入的第一行包含一个整数 tt(1≤t≤1e4 ) - 测试用例的数量。

每个测试用例的第一行包含两个整数 n 和 m ( 1≤n⋅m≤1e6 ) - 网格的行数和列数。

接下来的 n 行分别包含 m 个字符。每个字符都是". "或 "#"。

保证所有测试用例中 n⋅m 的总和不超过 1e6 。

大体思路：首先通过 (i-1)*m+j的方式将二维压缩为一维，后通过并查集将初始的连通块的个数算出来。后通过枚举每一行，每一列计算出最大的ans。 再计算每一行通过上下，计算每一列通过左右。注意再将每一个连通块合起来时，要用map,或set存储每个联通块的根节点（去重），最后统计ans.最后注意一下代码细节。

#include <bits/stdc++.h>
#define IOS ios::sync_with_stdio(0);cin.tie(0),cout.tie(0)
using namespace std;
using i64 = long long;
const int N = 2e6+7;
int tr[N];
int dp[N];
int n,m;
int go(int i,int j){ //打包
    return (i-1) * m + j;
}

int find(int x){
    if(tr[x] != x) {
        tr[x] = find(tr[x]);
    }
    return tr[x];
}

void memage(int a,int b){
    if(find(b) == find(a))return; //已经在的不加上
    dp[find(b)] += dp[find(a)];
    tr[find(a)] = find(b);
}

int dx[] = {0,1,0,-1};
int dy[] = {1,0,-1,0};
void solve(){
    cin >> n >> m;
    for(int i=1; i<=n*m; i++) { //初始化
        tr[i] = i;
        dp[i] = 0;
    }
    vector<string> g;
    g.push_back("***");
    for(int i=1; i<=n; i++) {
        string t;
        cin >> t;
        t = "*"+t;
        for(int j=1; j<=m; j++) {
            if(t[j]=='#')dp[go(i,j)] = 1;
            else dp[go(i,j)] = 0, tr[go(i,j)] = 0;
        }
        g.push_back(t);
    }

    for(int i=1; i<=n; i++) {
        for(int j=1; j<=m; j++) {
            if(g[i][j]=='.')continue;
            for(int k=0; k<4; k++) {
                int di = i+dx[k];
                int dj = j+dy[k];
                if(di<1 || dj < 1 || di>n || dj > m || g[di][dj]=='.')continue;
                memage(go(i,j), go(di,dj));
            }
        }
    }
    int ans = 0;
    for(int i=1; i<=n; i++) {
        int cnt = 0;//计算原来就有的'#',避免加多
        set<int> st;

        for(int j=1; j<=m; j++) {
            cnt += g[i][j]=='#';
            st.insert(find(go(i,j)));
            st.insert(find(go(max(i-1, 1), j)));
            st.insert(find(go(min(i+1, n), j)));
        }
        int sum = m-cnt;
        for(auto it : st) {
            sum += dp[it]; //it代表的每个要连起来的连通块的根节点
        }
        ans = max(ans, sum);
    }
    //同上枚举列
    for(int j=1; j<=m; j++) {
        int cnt = 0;
        set<int> st;
        for(int i=1; i<=n; i++) {
            cnt += g[i][j]=='#';
            st.insert(find(go(i,j)));
            st.insert(find(go(i, max(j-1, 1))));
            st.insert(find(go(i, min(j+1, m))));
        }
        int sum = n-cnt;
        for(auto it : st) {
            sum += dp[it];
        }
        ans = max(ans, sum);
    }

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

signed main(){
    IOS;
    int T = 1;
    cin >> T;
    while(T--) {
        solve();
    }
    return 0;
}

欢迎大佬指正，欢迎您的收看与点赞