记录编号	178293	评测结果	AAAAAAAAAAAAAAAAAAAA
题目名称	[NOIP 2010冲刺七]翻转游戏	最终得分	100
用户昵称	真红之蝶	是否通过	通过
代码语言	C++	运行时间	0.410 s
提交时间	2015-08-13 16:43:59	内存使用	0.35 MiB

#include<cstdio>
using namespace std;
char a[6][6];
int b[6][6],ans=0x7fffffff,tot1,tot2,dig[16]={32768,16384,8192,4096,2048,1024,512,256,128,64,32,16,8,4,2,1},kmp=0;
int flag[6][6];int v[6][6][6][6][17];
int minc(int a,int b)
{
	return (a<b)?a:b;
}
void dfs(int x,int y,int step,int dx,int dy)
{
    if(v[x][y][dx][dy][step]>32)
        return;
    v[x][y][dx][dy][step]++;
	int c=0,d=0;
	flag[x][y]=1;
	b[x][y]^=1;
	b[x-1][y]^=1;
	b[x+1][y]^=1;
	b[x][y-1]^=1;
	b[x][y+1]^=1;
	for(int i=1;i<=4;++i)
	    for(int j=1;j<=4;++j)
	        c=(b[i][j])?++c:c,d=(!b[i][j])?++d:d;
	if(c==16||d==16)
	{
	    ans=minc(ans,step);
	    flag[x][y]=0;
	    b[x][y]^=1;
     	b[x-1][y]^=1;
	    b[x+1][y]^=1;
    	b[x][y-1]^=1;
    	b[x][y+1]^=1;
    	return;
    } 
    for(int i=1;i<=4;++i)
        for(int j=1;j<=4;++j)
            if(!flag[i][j])
               dfs(i,j,step+1,x,y);
    flag[x][y]=0;
	b[x][y]^=1;
    b[x-1][y]^=1;
	b[x+1][y]^=1;
    b[x][y-1]^=1;
    b[x][y+1]^=1;
    return;
}
/*void bfs(int x,int step)
{
    if(x==0||x==((1<<16)-1))
    {
        ans=minc(ans,step);
    }
}*/
int main()
{
    freopen("flip.in","r",stdin);
    freopen("flip.out","w",stdout);
	for(int i=1;i<=4;++i)
	    scanf("%s",&a[i][1]);
	for(int i=1;i<=4;++i)
	    for(int j=1;j<=4;++j)
	        b[i][j]=(a[i][j]=='b')?0:1;
	for(int i=1;i<=4;++i)
	    for(int j=1;j<=4;++j)
	    {
	        tot1=(b[i][j])?++tot1:tot1;
	        tot2=(!b[i][j])?++tot2:tot2;
	    }
	if(tot1==16||tot2==16)
	{
		printf("0");
		getchar();getchar();getchar();getchar();
		return 0;
	}
	
	for(int i=1;i<=4;++i)
	    for(int j=1;j<=4;++j)
	        dfs(i,j,1,0,0);
/*	for(int i=1;i<=4;++i)
	    for(int j=1;j<=4;++j)
        {
            if(b[i][j])
                kmp+=(1<<(4*(i-1)+j));
        }*/
   /* bfs(kmp,0);*/
   if(ans==0x7fffffff)
       printf("Impossible");
    else
       printf("%d",ans);
	getchar();getchar();getchar();getchar();
    return 0;
}