はまやんはまやんはまやん

hamayanhamayan's blog

Alternating Path [AISing Programming Contest 2019 / エイシング プログラミング コンテスト 2019 C]

https://atcoder.jp/contests/aising2019/tasks/aising2019_c

解説

https://atcoder.jp/contests/aising2019/submissions/3985742

問題の言い換えをする必要がある。
隣接していて、色が異なっているマスの間に辺を張ったときの連結成分を考えると、
その中の黒は黒白黒白…でどの白にも行ける。
よって、連結成分について2グループの頂点数を数えて、その積をとったものが、その連結成分における組み合わせになる。
なので、
1. 連結成分毎に2グループの個数を集計
2. 集計した頂点数の積を答えに加える
を順次やっていけばいい。
 
これはdfsを使って数え上げればいい。
f(x, y) := 頂点(x,y)を含む連結成分の(グループAの個数, グループBの個数)
dfsをするが、訪問済みの頂点をチェックしながら、ループや重複を防いでいく。

int H, W; string S[404];
//---------------------------------------------------------------------------------------------------
int dx[4] = { 0, 1, 0, -1 }, dy[4] = { -1, 0, 1, 0 };
int vis[404][404];
pair<ll, ll> dfs(int x, int y) {
    vis[y][x] = 1;
 
    ll a = 1, b = 0;
    rep(i, 0, 4) {
        int xx = x + dx[i];
        int yy = y + dy[i];
        if (xx < 0 or W <= xx or yy < 0 or H <= yy) continue;
        if (vis[yy][xx]) continue;
        if (S[y][x] != S[yy][xx]) {
            auto p = dfs(xx, yy);
            a += p.second;
            b += p.first;
        }
    }
 
    return { a, b };
}
//---------------------------------------------------------------------------------------------------
void _main() {
    cin >> H >> W;
    rep(y, 0, H) cin >> S[y];
 
    ll ans = 0;
    rep(y, 0, H) rep(x, 0, W) if (!vis[y][x]) {
        auto p = dfs(x, y);
        ans += p.first * p.second;
    }
    cout << ans << endl;
}