ビット演算集大成の問題！？

ビット演算集大成の良問をPOJで見つけたので紹介。

実は、自分でも似たような問題を考えていてTopCoderに問題投稿しようかな・・と思ってましたが、似たような問題は既にありました。。

しかも、2次元バージョンでよりトリッキーな感じ。。

問題はこちら。

http://poj.org/problem?id=2965

簡単に日本語訳すると、

4*4マスに+と-の文字列がある。

（i, j）マスを選択すると、(i,j)マスが

+の場合は、-に

-の場合は、+に

反転変換できる。但し、(i,j)マスを選択すると、i行のマス及びj行のマスの値もすべて反転してしまう。

すべての文字を-にするためには、最低何回のマスを選択しないといけないか？

またそのときに選択するマスを列挙せよ。

んー、これ系の問題はメジャーなんですかね。。TopCoderでも似たような問題ありました。

ビット演算を使うと解けますが、実はこの問題はビット演算の使いどころが２種類あります。

①組み合わせをビットで表現する

②状態および処理をビット演算で計算し、処理を高速化

①は、どのマスを選択するかを0, 1のビットで表すという意味。

②は、4*4マスの状態を16bitのビットで保持します。さらに、あるマスを選択した場合の処理をXORを用いて実現します。

以下ソース。

int main() {
    int ch[16];
    REP(i,16) {
        ch[i] = 0;
        REP(k, 16)
            if (k/4 == i/4 || k%4 == i%4)
                ch[i] |= 1<<k;
    }

    string in;
    int ref = 0;

    REP(i, 4) {
        cin >> in;
        REP(j, 4)
            if (in[j] == '+')
                ref |= 1<<(4*i+j);
    }

    int ret = INF, bcomb = -1;
    REP(comb, 1<<16) {
        int ref_t = ref, cnt=0;
        REP(i, 16)
            if (comb >> i & 1)
                ref_t ^= ch[i], ++cnt;

        if (!ref_t && ret > cnt)
            ret = cnt, bcomb = comb;
    }
    cout << ret << endl;
    REP(i, 16)
        if (bcomb >> i & 1)
            cout << i/4+1 << " " << i%4+1 << endl;

    return 0;
}