村整備 [第四回 アルゴリズム実技検定 G]

https://atcoder.jp/contests/past202010-open/tasks/past202010_g

前提知識

• UnionFind

解説

https://atcoder.jp/contests/past202010-open/submissions/21472171

実装問題であるが、一部アルゴリズムを知っていることで実装が楽になる部分がある。
今回の問題のように「移動可能な隣接マスを経由することで互いに行き来可能である」という連結を管理する場合は
UnionFindというアルゴリズムを利用するのがいい。

まずは全探索

制約がとても小さいので、どの壁を取り外すかというのは全探索できる。
後はその壁を取り外した後で全体が行き来可能、1つの連結成分であるかを判定する。

連結成分かの判定

UnionFindを使おう。
自分は2D版に拡張したものを使って解いているが、普通に頂点(x,y)をx+y*WにマッピングしてUnionFindしているだけ。
どちらも'.'である隣接マスについて連結を行って最後にUnionFindの結果の個数を数えて1個（全部連結されている）なら答えに加える。

int H, W;
string S[10];
//---------------------------------------------------------------------------------------------------
void _main() {
    cin >> H >> W;
    rep(y, 0, H) cin >> S[y];

    int ans = 0;
    rep(sy, 0, H) rep(sx, 0, W) if (S[sy][sx] == '#') {
        S[sy][sx] = '.';
        UnionFind2D uf(H, W);
        rep(y, 0, H - 1) rep(x, 0, W) if (S[y][x] == '.' && S[y + 1][x] == '.') {
            uf.marge(x, y, x, y + 1);
        }
        rep(y, 0, H) rep(x, 0, W - 1) if (S[y][x] == '.' && S[y][x + 1] == '.') {
            uf.marge(x, y, x + 1, y);
        }
        set<pair<int, int>> s;
        rep(y, 0, H) rep(x, 0, W) if (S[y][x] == '.') s.insert(uf.get(x, y));

        if (s.size() == 1) ans++;

        S[sy][sx] = '#';
    }
    cout << ans << endl;
}