読者です 読者をやめる 読者になる 読者になる

AGC004 C - AND Grid

問題

agc004.contest.atcoder.jp

考察

「解は必ず存在することが示せます。」というアヤシイ一文があります。
何となく簡単な解法がありそうです。

赤と青はそれぞれが連結で、紫のマス以外は両方塗られていてはいけません。
そこで、まずは各マスがいずれかの色で塗られており、連結で、かつ色々なマスに伸ばせるという条件の基本形を考えます。

色々と考えてみると、そのような条件を満たすには、赤と青がアミアミで端だけくっついている、櫛2つのような形が良さそうです。
これさえ思いつけば、この基本形に加えて紫の所だけ両方の色で塗れば題意を満たす事ができます。

コード

int main() {
    int H, W;
    cin >> H >> W;
 
    vector<string> a(H);
    rep(i, H)
        cin >> a[i];
 
    vector<vector<char> > red(H, vector<char>(W, '.')),
            blue(H, vector<char>(W, '.'));
 
    REP(i, 1, H-1) {
        rep(j, W) {
            if(j % 2 == 0)
                red[i][j] = '#';
            else
                blue[i][j] = '#';
        }
    }
    rep(i, W) {
        red[0][i] = '#';
        blue[H-1][i] = '#';
    }
 
    REP(i, 1, H-1) {
        REP(j, 1, W-1) {
            if(a[i][j] == '#') {
                red[i][j] = '#';
                blue[i][j] = '#';
            }
        }
    }
 
    tr(it, red) {
        tr(it2, *it) cout << *it2;
        cout << endl;
    }
    tr(it, blue) {
        tr(it2, *it) cout << *it2;
        cout << endl;
    }
    
    return 0;
}

備考

閃きが大事な問題でした。
面白い。