POJ 1222: EXTENDED LIGHTS OUT

ほろ酔いコーディング

概要

5行6列のライトのついたボタンがあって，ボタンを押したらそのボタンと4近傍のボタンが反転する．
与えられた状態からライトを全部消す押し方を求める．

解法

蟻本まんま．幅と高さをいじればそのまま通用する．．．と思う．
僕は一から実装しました．

const int W = 6;
const int H = 5;

int di[] = {0, 0, 1, 0, -1};
int dj[] = {0, 1, 0, -1, 0};
int ans[10][10];
int tmp[10][10];
int f[10][10];
int M;
void solve(int s){
    memset(ans, 0, sizeof(ans));
    for(int j = 0; j < W; ++j) if(s >> j & 1){
        ans[1][j+1] = 1;
        for(int k=0;k<4;++k) tmp[1+di[k]][j+1+dj[k]] ^= 1;
    }
    for(int i=1;i<H;++i)for(int j=1;j<=W;++j){
        if(tmp[i][j]){
            ans[i+1][j] = 1;
            for(int k=0;k<5;++k) tmp[i+1+di[k]][j+dj[k]] ^= 1;
        }
    }
    bool f = true;
    for(int j=1;j<=W;++j) f = f && tmp[H][j] == 0;
    if(f){
        for(int i=1;i<=H;++i) for(int j = 1; j <= W; ++j)
            printf("%d%c", ans[i][j], j < W ? ' ':'\n');
    }
}
int main(){
    scanf("%d", &M);
    for(int m=1;m<=M;++m){
        for(int i = 0; i < H; ++i)for(int j = 0; j < W; ++j)
            scanf("%d", f[i]+j);
        printf("PUZZLE #%d\n", m);
        for(int s=0; s < 1 << W; ++s){
            for(int i=0;i<H;++i)for(int j=0;j<W;++j) 
                tmp[i+1][j+1] = f[i][j];
            solve(s);
        }
    }
    return 0;
}