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;
}