POJ-2965: The Pilots Brothers' refrigerator

keyword

ライツアウト　BruteForce　C++

問題概要

ルールの少し変わったサイズ4*4のボードでのライツアウト。最小手数を出力する問題。

解法

16マスしかないのでBruteForceでもギリギリ間に合いそう。このルールだと計算量はO(2^22)で間に合いそうだと思ったらTLEした。その後小手先の高速化で通った。

感想

連立1次方程式で解いた場合も最小性は保たれているんだろうか。真面目に考えてないけど、答えが存在する場合は最小になっている気がする。そもそも行列のrankはどうなっているんだろう。ちょっと前SRMのhardで出題されていた気がする。

#include <cstdio>
using namespace std;

char board[10][10];
char tmp[10][10];

bool check(int bit){
    for(int i=0; i<4; i++)for(int j=0; j<4; j++) tmp[i][j]=board[i][j];

    for(int i=0; i<4; i++)for(int j=0; j<4; j++)if((bit>>(i*4+j))&1){
        for(int k=0; k<4; k++) tmp[i][k] = tmp[i][k]=='-'?'+':'-';
        for(int k=0; k<4; k++) tmp[k][j] = tmp[k][j]=='-'?'+':'-';
        tmp[i][j] = tmp[i][j]=='-'?'+':'-';
    }

    for(int i=0; i<4; i++)for(int j=0; j<4; j++)
        if(tmp[i][j] == '+') return false;
    return true;
}

void solve(){
    int ans = 0;
    if(check(0)) goto end;
    for(int k=1;k<=16;k++){
        int comb = (1<<k) - 1;
        while(comb < 1<<16){
            if(check(comb)){
                ans = comb;
                goto end;
            }
            int x = comb & -comb, y = comb + x;
            comb = ((comb & ~y) / x >> 1) | y;
        }
    }
end:;
    printf("%d\n",__builtin_popcount(ans));
    for(int i=0; i<4; i++)for(int j=0; j<4; j++)if((ans>>(i*4+j))&1){
        printf("%d %d\n",i+1,j+1);
    }
}

int main(){
    for(int i=0; i<4; i++)
        gets(board[i]);
    solve();
    return 0;
}