记录编号	43472	评测结果	AAAAAAAAAAAAAAAAAAAA
题目名称	[NOIP 2010冲刺七]翻转游戏	最终得分	100
用户昵称	临轩听雨ゐ	是否通过	通过
代码语言	C++	运行时间	0.012 s
提交时间	2012-10-10 19:53:36	内存使用	3.12 MiB

#include <fstream>
#include <cstdlib>
#include <cstdio>
#include <cstring>
using namespace std;
ifstream in("flip.in");
ofstream out("flip.out");
int t;
bool a[6][6]={0},b[6][6]={0};
int ans1=0,ans2=0;

int minn(int i,int j)
{
    if(i<j)j=i;
    return j;
}

int work1(int x,int y,int z)
{
    int i,j,t;
    if(x==5)
	{
		t=1;
		for(i=1;t&&i<=4;i++)
			for(j=1;t&&j<=4;j++)
				if(a[i][j]==1)
					t=0;
				if(t)
					ans1=minn(ans1,z);
		return 0;
	}
    if(y==5)
		return work1(x+1,1,z);
    if(x==5&&y>=2&&a[x][y-1]!=0)
		return 0;
    if(x>=2&&y>=2&&a[x-1][y-1]!=0)
		return 0;
    if(a[x-1][y]==0)
		work1(x,y+1,z);
    a[x-1][y]^=1;a[x][y-1]^=1;a[x][y]^=1;
    a[x][y+1]^=1;a[x+1][y]^=1;
	
    work1(x,y+1,z+1);
	
    a[x-1][y]^=1;a[x][y-1]^=1;a[x][y]^=1;
    a[x][y+1]^=1;a[x+1][y]^=1;
    return 0;
}
int work2(int x,int y,int z)
{
    int i,j,t;
    if(x==5)
	{
		t=1;
		for(i=1;t&&i<=4;i++)
			for(j=1;t&&j<=4;j++)
				if(b[i][j]==0)
					t=0;
				if(t)
					ans1=minn(ans1,z);
		return 0;
	}
    if(y==5)return work2(x+1,1,z);
    if(x==5&&y>=2&&b[x][y-1]!=1)
		return 0;
    if(x>=2&&y>=2&&b[x-1][y-1]!=1)
		return 0;
    if(b[x-1][y]==1)
		work2(x,y+1,z);
    b[x-1][y]^=1;b[x][y-1]^=1;b[x][y]^=1;
    b[x][y+1]^=1;b[x+1][y]^=1;
	
    work2(x,y+1,z+1);
	
    b[x-1][y]^=1;b[x][y-1]^=1;b[x][y]^=1;
    b[x][y+1]^=1;b[x+1][y]^=1;
    return 0;
}

int main()
{
    int i,j;
    memset(b,1,sizeof(b));
    char c;
	bool aa=false,bb=false;
    for(i=1;i<=4;i++)
	{
		for(j=1;j<=4;j++)
		{
			in>>c;
			if(c=='b')
			{
				b[i][j]=0;
				aa=true;
			}else{
				a[i][j]=1;
				bb=true;
			}
		}
	}
	if((aa==true&&bb==false)||(aa==false&&bb==true))
	{
		out<<0<<endl;
	}else{
		ans1=ans2=1000000;
		t=1;
		work1(1,1,0);
		t=1;
		work2(1,1,0);
		if(ans1<ans2)
			ans2=ans1;
		if(ans2==1000000)
			out<<"Impossible";
		else out<<ans2;
	}
    return 0; 
}