広告 [SoundHound Inc. Programming Contest 2018 (春) C]

https://soundhound2018.contest.atcoder.jp/tasks/soundhound2018_c

前提知識

• 二部グラフでの最大独立集合問題

解法

https://soundhound2018.contest.atcoder.jp/submissions/2025646

今回の問題は「セルを頂点、隣接関係を辺と考えた二部グラフでの最大独立集合問題」となる。
これに気付くのも簡単じゃないと思うが、制約や経験から思いつくしか無いように思う。
　
二部グラフでの最大独立集合の答えは「頂点数-最大マッチング数」となる。
なので、二部グラフを構成して最大マッチング数を求めよう。
頂点数は、H*Wではなく'.'である頂点数を使おう。

int H, W;
string C[50];
//---------------------------------------------------------------------------------------------------
void _main() {
    cin >> H >> W;
    rep(y, 0, H) cin >> C[y];
 
    int N = H * W;
    BipartiteMatching bm(N, N);
    rep(y, 0, H) rep(x, 0, W) {
        if ((y + x) % 2 == 0) {
            if(x < W - 1) if (C[y][x] == '.' and C[y][x + 1] == '.') bm.add_edge(y * W + x, y * W + x + 1);
            if(y < H - 1) if (C[y][x] == '.' and C[y + 1][x] == '.') bm.add_edge(y * W + x, (y + 1) * W + x);
        }
        else {
            if (x < W - 1) if (C[y][x] == '.' and C[y][x + 1] == '.') bm.add_edge(y * W + x + 1, y * W + x);
            if (y < H - 1) if (C[y][x] == '.' and C[y + 1][x] == '.') bm.add_edge((y + 1) * W + x, y * W + x);
        }
    }
 
    int ans = -bm.match();
    rep(y, 0, H) rep(x, 0, W) if (C[y][x] == '.') ans++;
    cout << ans << endl;
}