ABC 351

Table of Contents

D - Grid and Magnet

https://atcoder.jp/contests/abc351/tasks/abc351_d

3時間近くかかったが自力 AC

磁石が置かれていないマスを空マスと呼ぶことにする。 磁石と隣接していない空マス同士を union-find で連結する。 連結部分のサイズと連結部分の外縁にある磁石と隣接する空マスの数の合計のうち最大値を出力する。

int h, w;
vector<string> grid;
vvint memo;
vvint visited;
vint di = {0, 1, 0, -1};
vint dj = {1, 0, -1, 0};

pair<int, int> ind2sub(int x) {
    return {x / w, x % w};
}

int sub2ind(int i, int j) {
    return i * w + j;
}

int canMove(int i, int j) {
    int ok = 1;
    rep(d, 4) {
        int ni = i + di[d], nj = j + dj[d];
        if (clamp(ni, 0, h - 1) != ni || clamp(nj, 0, w - 1) != nj)
            continue;
        if (grid[ni][nj] == '#')
            ok = 0;
    }

    return ok;
}

void solve() {
    cin >> h >> w;
    grid = vector<string>(h);
    rep(i, h) cin >> grid[i];

    dsu uf(h * w);

    rep(i, h) rep(j, w) {
        if (grid[i][j] == '.' && canMove(i, j)) {
            for (auto [ii, jj] : vector<pair<int, int>>({{1, 0}, {0, 1}})) {
                int ni = i + ii, nj = j + jj;
                if (clamp(ni, 0, h - 1) != ni || clamp(nj, 0, w - 1) != nj)
                    continue;
                if (canMove(ni, nj)) {
                    uf.merge(sub2ind(i, j), sub2ind(ni, nj));
                }
            }
        }
    }

    int ans = 1;
    for (auto v : uf.groups()) {
        set<pair<int, int>> stop;
        {
            auto [i, j] = ind2sub(v[0]);
            if (grid[i][j] == '#')
                continue;
            else if (!canMove(i, j)) {
                continue;
            }
        }
        for (int id : v) {
            auto [i, j] = ind2sub(id);
            rep(d, 4) {
                int ni = i + di[d], nj = j + dj[d];
                if (clamp(ni, 0, h - 1) != ni || clamp(nj, 0, w - 1) != nj)
                    continue;
                if (grid[ni][nj] == '.' && !canMove(ni, nj))
                    stop.insert({ni, nj});
            }
        }
        chmax(ans, (int)v.size() + (int)stop.size());
    }

    cout << ans << endl;
}