poj 1753 Flip Game （bfs + 枚舉）

poj 1753 Flip Game （bfs + 枚舉）

鏈接：poj 1753

題意：這是翻棋游戲，給定4*4棋盤，棋子一面為黑色（用b表示），另一面為白色（用w表示），問至少要幾步可以將棋子翻為全黑或者全白，如不能達到目的，輸出“Impossible ”

翻轉規則：可以選定16個棋子中的任意一個，將其本身以及上下左右相鄰的翻轉過來

分析：其實每格棋子最多只可以翻轉一次（實際是奇數次，但與翻轉一次狀態一樣），只要其中一格重復翻了2次(不論是連續翻動還是不連翻動)，那麼它以及周邊的棋子和沒翻動時的狀態是一致的，與最初狀態未翻轉一樣，由此就可以確定這個棋盤最多只能翻16步，最多只能有翻出2^16種狀態

思路：可以直接dfs枚舉所有狀態，直到找到目標狀態

#include
int step,flag,x[5]={0,0,0,1,-1},y[5]={1,-1,0,0,0};
char s[5][5];
int judge()              //判斷是否為全黑或全白
{
    int i,j;
    for(i=0;i<4;i++)
        for(j=0;j<4;j++)
            if(s[i][j]!=s[0][0])
                return 0;
    return 1;
}
void flip(int r,int c)               //翻轉棋子
{
    int i,j,k;
    for(k=0;k<5;k++){
        i=r+x[k];
        j=c+y[k];
        if(i>=0&&i<4&&j>=0&&j<4){
            if(s[i][j]=='b')
                s[i][j]='w';
            else
                s[i][j]='b';
        }
    }
}
void dfs(int i,int j,int cnt)
{
    if(cnt==step){
        flag=judge();
        return ;
    }
    if(flag||i==4)
        return ;
    flip(i,j);     //翻轉棋子
    if(j<3)
        dfs(i,j+1,cnt+1);
    else
        dfs(i+1,0,cnt+1);
    flip(i,j);         //回溯
    if(j<3)
        dfs(i,j+1,cnt);
    else
        dfs(i+1,0,cnt);
    return ;
}
int main()
{
    int i;
    for(i=0;i<4;i++)
        scanf("%s",s[i]);
    for(step=0;step<=16;step++){      //最多翻轉16次
        dfs(0,0,0);
        if(flag)
            break;
    }
    if(flag)
        printf("%d\n",step);
    else
        printf("Impossible\n");
    return 0;
}