程式碼備份區

題意：

給4*4的黑白棋盤，如果翻牌的話可以讓自己以及四周的人交換黑白狀態

問說最少用幾步可以把全部換成黑或全部換成白

解法：

開關燈問題，窮舉第一排按法，然後第二排之後依照第一排的狀態讓棋盤變成黑或白

最後檢查有沒有全黑或全排，紀錄最小步數

程式碼：

#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#define INF 1<<29
char map[6][6];
char game[6][6];
char change[256];
int move[5][2] = { {0,0},{1,0},{0,1},{-1,0},{0,-1} };
void copy(){
    int i,j;
    for(i=1;i<=4;++i){
        for(j=1;j<=4;++j){
            game[i][j] = map[i][j];
        }
    }
}
void push(int x,int y){
    int i;
    for(i=0;i<5;++i){
        game[x+move[i][0]][y+move[i][1]] = !game[x+move[i][0]][y+move[i][1]];
    }
}
int solve(int num,int type){
    int i,j;
    for(i=2;i<=4;++i){
        for(j=1;j<=4;++j){
            if(game[i-1][j] != type){
                push(i,j);
                ++num;
            }
        }
    }
    for(j=1;j<=4 && game[4][j]==type;++j);
    if(j>4)return num;
    return INF;
}
int main(){
    int i,j;
    int num,ans;
    change['b'] = 0;
    change['w'] = 1;
    while(scanf("%s",&map[1][1])!=EOF){
        ans = INF;
        for(i=2;i<=4;++i){
            scanf("%s",&map[i][1]);
        }
        for(i=1;i<=4;++i){
            for(j=1;j<=4;++j){
                map[i][j] = change[(int)(map[i][j])];
            }
        }

        for(i=0;i<32;++i){
            copy();
            for(j=num=0;j<4;++j){
                if((i&(1<<j))>0){
                    push(1,j+1);
                    ++num;
                }
            }
            num = solve(num,i/16);
            if(ans>num)ans=num;
        }
        if(ans<INF)printf("%d\n",ans);
        else puts("Impossible");
    }
    return 0;
}