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

ビット演算集大成の良問を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を用いて実現します。

以下ソース。

view plainprint?

1. int main() {  
2.     int ch[16];  
3.     REP(i,16) {  
4.         ch[i] = 0;  
5.         REP(k, 16)  
6.             if (k/4 == i/4 || k%4 == i%4)  
7.                 ch[i] |= 1<<k;  
8.     }  
9.   
10.     string in;  
11.     int ref = 0;  
12.   
13.     REP(i, 4) {  
14.         cin >> in;  
15.         REP(j, 4)  
16.             if (in[j] == '+')  
17.                 ref |= 1<<(4*i+j);  
18.     }  
19.   
20.     int ret = INF, bcomb = -1;  
21.     REP(comb, 1<<16) {  
22.         int ref_t = ref, cnt=0;  
23.         REP(i, 16)  
24.             if (comb >> i & 1)  
25.                 ref_t ^= ch[i], ++cnt;  
26.   
27.         if (!ref_t && ret > cnt)  
28.             ret = cnt, bcomb = comb;  
29.     }  
30.     cout << ret << endl;  
31.     REP(i, 16)  
32.         if (bcomb >> i & 1)  
33.             cout << i/4+1 << " " << i%4+1 << endl;  
34.   
35.     return 0;  
36. }  

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;
}