スイッチ問題まとめ【難解なスイッチ】|【Fliptile(poj)】【消灯】(検索?)(状圧?)(ビット演算?)(テクニック列挙?)

概要:
経典例題:POJ 3279
01行列をあげます.行列の大きさはMxNです.(1<=M,N<=15)操作ごとに1つの格子が選択され、その格子が上下左右の4つの格子の値と反転する.マトリクス内のすべての値を0にするには、少なくとも何回の操作が必要ですか?反転シナリオを出力してください.シナリオがなければ、「IMPOSIBLE」を出力します.複数のシナリオが問題に合致する場合は、まず反転回数が最も少ないシナリオを出力してください.シナリオの個数が一意でない場合は、辞書順が最も小さいシナリオを出力します.
入力:
4 4 1 0 0 1 0 1 1 0 0 1 1 0 1 0 0 1
出力:
0 0 0 0 1 0 0 1 1 0 0 1 0 0 0 0
このような問題には、問題の意味がどんなに複雑であっても、最終的に反転の最小回数を出力しても、行列の形で各行の各ブロックを出力しても、核心的な問題はいつも:あなたは各ブロックを反転することができて、目的はすべてのブロックを完全に同じように見せることです.では、どのように反転しますか.
テクニック:
一、ビット演算:まずビット演算は簡略化技術であり、直接ビット演算を借りて解決する問題は少ない(しかし難題が多い)が、多くのアルゴリズムはビット演算から離れられない(状態圧縮、ST).また,ビット演算は直接バイナリと付き合っているので,効率は通常の計算よりどれだけ速いか分からない.したがって、ビット演算を合理的に利用することは良いテクニックです.
いくつかの例を挙げます.
1、a^=1は、aが表すバイナリを1ビットずつ反転し、0が1、1が0になることを表す.
2、偶数と1異はこの数に1を加え、奇数と1異はこの数に1を減らす.
3、二分はよく使われる(r+l)>>1で、2で割ることに相当する.
4、1<<5は2の5次方に相当し、その原理も簡単で、1に対応するバイナリ数を5ビット左にシフトし、後に0を補うという演算はpowよりずっと速い.
もちろんビット演算では精度の問題を処理できない場合があります.例えばa^=bを使います.b^=a;a^=b;swapの代わりにdoubleタイプを処理できません.
長さmのbool配列をmビットのバイナリ数で表すバイナリ状態圧縮

整数nのバイナリ表現におけるk番目のビット(n>>k)&1

を取り出す.

整数nをバイナリ表示で0~k-1位(後k位)n&((1<

整数nをバイナリ表示でk番目に逆n xor(1<

整数nのバイナリ表現におけるk番目のビット付与値を1 n|(1<

整数nを取り出してバイナリ表示でのkビット付与値0 n&(~(1<

二、方向配列

int x[4] = {0, 0, -1, 1};//    
int y[4] = { -1, 1, 0, 0};//    

for(int k = 0; k < 4; ++k)//       ，     ，       
        if(i + x[k] > -1 && j + y[k] > -1)
            t[i + x[k]][j + y[k]] ^= 1;
}

方向配列を借りて、上下左右の4つの方向を遍歴することができます.本題はこの4つの方向を遍歴するだけです.いくつかの問題では、より複雑な方向配列が必要です.
三、memcpy
memcpy(t, g, sizeof(t));配列をコピーし、tはコピー、gは元
このような問題を分析します.
このような問題に戻りましょう.私たちの目的はすべてのブロックを同じ色にすることです.通常の考え方では、最初の行を同じ色にすることができます.最初の行は上境界なので、2番目の行を反転することでしか変更できません.2行目のブロックの一部を反転する方法です.この場合、2行目を同じ色にするには、3行目を反転するだけです.だから、私たちがある色を変えるたびに、この下の部分を反転するだけです(上を反転すると散らかります).では、マトリクス全体を同じ色に変え、最初の行の状態をどのように変えるかで、マトリクス全体が同化できるかどうかを決定し、最後の行をめくって最後の行に異なる色があることを発見すると、このスキームは望ましくないことを示します.問題は一般的に私たちが最小限の反転回数を出力する必要があります.最適なステップを見つけるには、最初のローのすべてのステータスを列挙する必要があります.
コード実装(√):
いくつかのグローバル変数

const int N = 16;
int g[N][N], t[N][N], f[N][N];
int cnt, n, m;
int x[4] = {0, 0, -1, 1};//    
int y[4] = { -1, 1, 0, 0};//    

モジュール化プログラミング(関数)は、まず次のように反転します.
0が1,1,0になる

void flip(int i, int j)//  
{
    ++cnt, f[i][j] = 1;//   1，         
    t[i][j] = !t[i][j];//      
    for(int k = 0; k < 4; ++k)//       ，     ，       
        if(i + x[k] > -1 && j + y[k] > -1)
            t[i + x[k]][j + y[k]] ^= 1;
}

行ごとに操作して、まず最初の行の状況を探し出します

bool ok(int k)//           ，             
{
    cnt = 0;//     
    memcpy(t, g, sizeof(t));//       ，         
    for(int j = 0; j < m; ++j)
        if(k & (1 << ((m - 1) - j)))
            flip(0, j);//       0，           
//-------------------------------------------------------------------------------------//
//-------------------------------        ---------------------------------------//
    for(int i = 1; i < n; ++i)
        for(int j = 0; j < m; ++j)
            if(t[i - 1][j]) flip(i, j);//          1，         ，      

    for(int j = 0; j < m; ++j)//           ，                    ，  1 return false
        if(t[n - 1][j]) return false;
    return true;
}

プライマリ関数では、主に最初の行のバイナリがすべての状況を表す列挙であり、最小ステップが見つかります.

int main()
{
    int ans, p;
    while(~scanf("%d%d", &n, &m))
    {
        for(int i = 0; i < n; ++i)//    
            for(int j = 0; j < m; ++j)
                scanf("%d", &g[i][j]);
//-------------------------------------------------------------------------------
        ans = n * m + 1, p = -1;//   
//-------------------------------------------------------------------------------
        for(int i = 0; i < (1 << m); ++i){//i        ，              ， 0001        
            if(ok(i) && cnt < ans) //                   ，      
                ans = cnt, p = i;
        }
        memset(f, 0, sizeof(f));
//--------------------------------------------------------------------------------
        if(p >= 0)//            ，    ，    
        {
            ok(p);
            for(int i = 0; i < n; ++i)
                for(int j = 0; j < m; ++j)
                    printf("%d%c", f[i][j], j < m - 1 ? ' ' : '
');
        }
        else puts("IMPOSSIBLE");//    
    }
}

コードの一部はcorfulsharkから