AISing Programming Contest 2019：C - Alternating Path

atcoder.jp

方針

マスの上から h 行目・左からw列目の点を (h, w) とします。

適当な点 (h, w) から出発し、白→黒→白→……、または黒→白→黒→…… で辿り付ける点すべてを X で置き換えます。こうして X となったマスの中の、任意の黒と任意の白の組は問題文の条件を満たしますので、(黒の数)×(白の数) で の組の数が分かります。

(追記)
答えは int に収まらない場合があります。例えば市松模様(白黒が交互に並んだ模様)で、かつ H = W = 400 のとき、 (400*400/2)*(400*400/2) = 6.4*10^9 通りとなります。ずっとこれに気付かずハマっていました。教えて下さった方、ありがとうございます。

具体例

入力例 1 の場合で説明します。(1, 1) から出発し、ここから辿れる点すべてをたどります。

.#.    X#.    XX.    XXX    XXX    XXX
..# -> ..# -> ..# -> .X# -> .XX -> .XX
#..    #..    #..    #..    #..    #.X

このとき X で置き換えた点のうち黒は2個、白は4個なので、条件を満たす白と黒のマスの組み合わせの数は、8通りとなります。

次は (2, 1) から出発すると、以下のようになります。

XXX    XXX    XXX    XXX
.XX -> XXX -> XXX -> XXX
#.X    #.X    X.X    XXX

このとき X で置き換えた点のうち黒は1個、白は2個なので、条件を満たす白と黒のマスの組み合わせの数は、2通りとなります。

以上2つを合わせて、答えは10通りです。

ソースコード

#include <bits/stdc++.h>
using namespace std;

int H, W;
vector<string> S;
vector<vector<int>> reach;
long long cntBlack = 0;
long long cntWhite = 0;

void search(int h, int w){
    if(S[h][w]=='#') cntBlack++;
    if(S[h][w]=='.') cntWhite++;

    reach[h][w] = 1;
    int dh[4] = {-1, 1, 0, 0};
    int dw[4] = {0, 0, -1, 1};
    for(int i=0; i<4; i++){
        int nh = h + dh[i];
        int nw = w + dw[i];
        if(0 <= nh && nh < H && 0 <= nw && nw < W && S[nh][nw] != S[h][w] && reach[nh][nw] == 0){
            search(nh,nw);
        }    
    }
}

int main(){
    cin >> H >> W;
    S = vector<string>(H);
    reach = vector<vector<int>>(H, vector<int>(W, 0));  // S[h][w]が X のとき reach[h][w] = 1,  X でないとき reach[h][w] = 0。
    for(int i=0; i<H; i++)  cin >> S[i];

    long long ans = 0;
    for(int h=0; h<H; h++){
        for(int w=0; w<W; w++){
            cntBlack = 0;
            cntWhite = 0;
            if(reach[h][w] != 1){    
                search(h,w);
                ans += cntBlack*cntWhite;
            }
        }
    }
    cout << ans << endl;
}