记录编号	178185	评测结果	AAAAAAAAAAAAAAAAAAAA
题目名称	[NOIP 2010冲刺七]翻转游戏	最终得分	100
用户昵称	forever	是否通过	通过
代码语言	C++	运行时间	0.094 s
提交时间	2015-08-13 14:09:22	内存使用	0.32 MiB

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<map>
#include<cstring>
#include<string>
#include<cmath>
#include<ctime>
#include<algorithm>
#include<queue>
#include<stack>
using namespace std;
char ch;
int b[18][8][8],num[3],ans=9999999;
int a[8][8],c[8][8],sum,k;
void getcnt()
{
	sum=0;
    for(int i=1;i<=4;++i)
     for(int j=1;j<=4;++j)
        c[i][j]=++sum;
   for(int k=1;k<=16;++k)
    for(int i=1;i<=4;++i)
      for(int j=1;j<=4;++j)
    	{   if(c[i][j]==k)
    		   	{b[k][i][j]=1;b[k][i][j+1]=1;b[k][i][j-1]=(j-1>0)?1:0;b[k][i+1][j]=1;b[k][i-1][j]=(i-1>0)?1:0;}
    	}
}
void dfs(int y,int s)
{   if(s>ans) return;
    int bv[8][8];
    memset(num,0,sizeof(num));
	for(int i=1;i<=4;++i)
	 for(int j=1;j<=4;++j)
	 {  num[b[0][i][j]]++;
	 	bv[i][j]=b[0][i][j];
	 }
	 if(num[1]==16||num[0]==16)
	 {  memset(num,0,sizeof(num));
	 	ans=min(s,ans);
	 	return;
	 }
	 if(y>16)
	   return;
	for(int i=1;i<=4;++i)
	 for(int j=1;j<=4;++j)
	 {
	 	b[0][i][j]=(b[0][i][j]^b[y][i][j]);
	 }
	dfs(y+1,s+1);
	for(int i=1;i<=4;i++)
	 for(int j=1;j<=4;j++)
	 {
	 	b[0][i][j]=bv[i][j];
	 }
	dfs(y+1,s);
}
int main()
{   freopen("flip.in","r",stdin);
    freopen("flip.out","w",stdout);
	for(int i=1;i<=4;++i)
	 for(int j=1;j<=4;++j)
	   {
	   	  cin>>ch;
	   	  if(ch=='w'){
	   	   	b[0][i][j]=1;num[1]++;
	   	   }
	   	  if(ch=='b'){
	   	   	 b[0][i][j]=0;num[0]++;
	   	   }
	   }
    if(num[0]==16||num[1]==16)
    {
    	puts("0");
    	return 0;
    }
    getcnt();
    memset(num,0,sizeof(num));
	dfs(1,1);
	if(ans>9999)
	 puts("Impossible");
    else
	 printf("%d",ans-1);
}