Flip Game

Flip Game

题目链接
思路：
这是一道典型的DFS题目，通过DFS枚举每一种情况，每个棋子都只有两种情况（非黑即白），所以共有2^n种情况，然后判断每种情况是否可以成立，并同时比较所需步骤大小。

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
int a[4][4];
int Min=0x7fffffff;
int check()//检查棋子是否同色
{
    int i,j;
    for(i=0; i<4; ++i)
        for(j=0; j<4; ++j)
            if(a[i][j]!=a[0][0])
                return -1;
    return 1;
}
void change(int i,int j)
{
    a[i][j]=!a[i][j];
    if(i-1>=0)
    {
        a[i-1][j]=!a[i-1][j];
    }
    if(j-1>=0)
    {
        a[i][j-1]=!a[i][j-1];
    }
    if(i+1<4)
    {
        a[i+1][j]=!a[i+1][j];
    }
    if(j+1<4)
    {
        a[i][j+1]=!a[i][j+1];
    }
}
void dfs(int d,int k)
{
    int x,y;
    if(d==16)
    {
        if(check()==1)
            if(k<Min)
                Min=k;
        return;
    }
    else
    {
        x=d/4;//行
        y=d%4;//列
        dfs(d+1,k);//没有翻的时候进行一次dfs 
        change(x,y); //翻过去
        dfs(d+1,k+1);//翻过去以后进行一次dfs 
        change(x,y);  //别忘了翻回去,这个是返回原来的状态
    }
}
int main()
{
    char t;
    for(int i=0;i<4;i++)
    {
        for(int j=0;j<4;j++)
        {
            cin>>t;
            if(t=='b') a[i][j]=0;
            else a[i][j]=1;
        }
    }
    dfs(0,0);
    if(Min==0x7fffffff)
        cout<<"Impossible"<<endl;
    else
        cout<<Min<<endl;
 
return 0;
}