Submission #52883999

---

Source Code Expand

// #pragma GCC optimize("Ofast,unroll-loops")
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define inf (ll)1e18
#define pll pair<ll, ll>
#define vi vector<int>
#define vl vector<ll>
#define fi first
#define se second
#define lll __int128
const int N = 1005, M = 1e6 + 5;
char g[N][N];
ll ds[4][2] = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
ll d[N][N], h, w;
bool vis[N][N];

ll fa[M];
ll find(ll x){
    if(fa[x] == x) return x;
    return fa[x] = find(fa[x]); //路径压缩
}
void merge(ll x, ll y){
    fa[find(x)] = find(y);
}
bool check(ll x, ll y) {
    for (ll k = 0; k < 4; k++) {
        ll nx = x + ds[k][0], ny = y + ds[k][1];
        if (nx < 1 || nx > h || ny < 0 || ny > w) {
            continue;
        }
        if (g[nx][ny] == '#')
            return true;
    }
    return false;
}
ll id(ll x, ll y) {
    return (x - 1) * w + y;
}
void solve() {
    cin >> h >> w;
    for (ll i = 1; i <= h; i++)
        for (ll j = 1; j <= w; j++)
            cin >> g[i][j];
    for (ll i = 1; i <= h; i++)
        for (ll j = 1; j <= w; j++)
            fa[id(i, j)] = id(i, j);
    ll ans = 0;
    for (ll i = 1; i <= h; i++) {
        for (ll j = 1; j <= w; j++) {
            if (g[i][j] == '#')
                continue;
            else
            	ans = 1;
            for (ll k = 0; k < 4; k++) {
                ll ni = i + ds[k][0], nj = j + ds[k][1];
                if (ni < 1 || ni > h || nj < 1 || nj > w || g[ni][nj] == '#')
                    continue;
                if (!check(i, j) && !check(ni, nj)) {
//                    cout << i << " " << j << " " << ni << " " << nj << endl;
                    merge(id(i, j), id(ni, nj));
                }
            }
        }
    }
    map<ll, ll> mp;
    for (ll i = 1; i <= h; i++) {
        for (ll j = 1; j <= w; j++) {
            if (g[i][j] != '#' && !check(i, j)) {
                ll r = id(i, j);
                ll rr = find(r);
                mp[find(id(i, j))]++;
            }
        }
    }
    for (ll i = 1; i <= h; i++) {
        for (ll j = 1; j <= w; j++) {
            if (g[i][j] == '#' || !check(i, j))
                continue;
            set<ll> st;
            for (ll k = 0; k < 4; k++) {
                ll ni = i + ds[k][0], nj = j + ds[k][1];
                if (ni < 1 || ni > h || nj < 1 || nj > w || g[ni][nj] == '#')
                    continue;
                if (!check(ni, nj)) {
                    ll r = find(id(ni, nj));
//                    cout << r << " " << i << " " << j << endl;
                    if (!st.count(r)) {
                        mp[r]++;
                        st.insert(r);
                    }

                }
            }
        }
    }
    for (auto [x, y] : mp)
        ans = max(ans, y);
    cout << ans << endl;
}
int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    solve();
    return 0;
}

Submission Info

Compile Error

Main.cpp: In function ‘void solve()’:
Main.cpp:71:20: warning: unused variable ‘rr’ [-Wunused-variable]
   71 |                 ll rr = find(r);
      |                    ^~

Judge Result