UnKoder #07 C Grid Coloring

2015/06/20 (Sat) hackerrank UnKoder アドホック

問題

問題文

方針

グリッドは二部グラフなので，連結成分ごとに塗り方は 2 通りしか無い． 各連結成分で両方試して多い方を採用していく．

実装

char col[] = "BR";

int H,W;

int draw(int ci, int cj, vector<string> & g, int add){
    int di[] = {0,1,0,-1};
    int dj[] = {1,0,-1,0};
    g[ci][cj] = col[(ci+cj+add)%2];
    int res = 0;
    if(g[ci][cj] == 'R') res++;
    rep(d,4){
        int ni = ci + di[d], nj = cj + dj[d];
        if(ni < 0 || nj < 0 || ni >= H || nj >= W) continue;
        if(g[ni][nj] != '.') continue;
        res += draw(ni, nj, g, add);
    }
    return res;
}

signed main(){
    ios_base::sync_with_stdio(0); cin.tie(0);
    cin >> H >> W;
    vector<string> g(H);
    rep(i,H) cin >> g[i];
    int ans = 0;
    rep(i,H)rep(j,W){
        if(g[i][j] != '.') continue;
        auto g1 = g, g2 = g;
        int x = draw(i,j,g1,1);
        int y = draw(i,j,g2,0);
        g = x > y ? g1 : g2;
        ans += max(x,y);
    }
    cout << ans << endl;
}