cf round952 h1tle求调
查看原帖
cf round952 h1tle求调
878738
gaiaking楼主2024/6/13 16:02
#include <bits/stdc++.h>

using namespace std;

const int N = 1e6 + 10;

int p[N];
int dx[4] = {-1, 1, 0, 0};
int dy[4] = {0, 0, -1, 1};

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

void solve() {
    int n, m;
    cin >> n >> m;
    vector<vector<char>> g((n + 2), vector<char>(m + 2));
    vector<vector<bool>> st((n + 2), vector<bool>(m + 2));
    vector<int> _size(N);
    for(int i = 0; i <= n * m; i ++ ) {
        p[i] = i;
        _size[i] = 1;
    }
    
    for(int i = 0; i <= m + 1; i ++ ) {
        g[0][i] = '.';
        g[n + 1][i] = '.';
    }
    
    for(int i = 0; i <= n + 1; i ++ ) {
        g[i][0] = '.';
        g[i][m + 1] = '.';
    }

    for(int i = 1; i <= n; i ++ ) {
        for(int j = 1; j <= m; j ++ ) {
            cin >> g[i][j];
        }
    }
    
    function<void(int, int)> bfs = [&](int a, int b) {
        queue<pair<int, int>> q;
        q.push({a, b});
        st[a][b] = true;
        while(q.size()) {
            auto t = q.front();
            q.pop();
            int pa = find((t.first - 1) * m + t.second);
            for(int i = 0; i < 4; i ++ ) {
                int x = t.first + dx[i];
                int y = t.second + dy[i];
                if(!st[x][y] && x >= 1 && x <= n && y >= 1 && y <= m && g[x][y] == '#') {
                    st[x][y] = true;
                    q.push({x, y});
                    int pb = find((x - 1) * m + y);
                    p[pb] = pa;
                    _size[pa] += _size[pb];
                }
            }
        }
    };
    
    for(int i = 1; i <= n; i ++ ) {
        for(int j = 1; j <= m; j ++ ) {
            if(!st[i][j] && g[i][j] == '#') {
                bfs(i, j);
            }
        }
    }
    
    int ans = 0;
    for(int i = 1; i <= n; i ++ ) {
        int res = 0;
        vector<bool> st(N);
        for(int j = 1; j <= m; j ++ ) {
            if(g[i][j] == '.') {
                res ++;
                if(g[i - 1][j] == '#') {
                    int fa = find(p[(i - 2) * m + j]);
                    if(!st[fa]) {
                        res += _size[fa];
                        st[fa] = 1;
                    }
                }
                
                if(g[i + 1][j] == '#') {
                    int fa = find(p[i * m + j]);
                    if(!st[fa]) {
                        res += _size[fa];
                        st[fa] = 1;
                    }
                }
            } else {
                int fa = find((i - 1) * m + j);
                if(!st[fa]) {
                    st[fa] = 1;
                    res += _size[fa];
                }
            }
        }
        ans = max(ans, res);
    }

    for(int j = 1; j <= m; j ++ ) {
        int res = 0;
        vector<bool> st(N);
        for(int i = 1; i <= n; i ++ ) {
            if(g[i][j] == '.') {
                res ++;
                if(g[i][j - 1] == '#') {
                    int fa = find(p[(i - 1) * m + j - 1]);
                    if(!st[fa]) {
                        res += _size[fa];
                        st[fa] = 1;
                    }
                }
                
                if(g[i][j + 1] == '#') {
                    int fa = find(p[(i - 1) * m + j + 1]);
                    if(!st[fa]) {
                        res += _size[fa];
                        st[fa] = 1;
                    }
                }
            } else {
                int fa = find((i - 1) * m + j);
                if(!st[fa]) {
                    st[fa] = 1;
                    res += _size[fa];
                }
            }
        }
        ans = max(ans, res);
    }
    cout << ans << endl;
}

int main() {
    int t;
    cin >> t;
    while(t -- ) {
        solve();
    }
    return 0;
}
2024/6/13 16:02
加载中...