记录编号	287766	评测结果	AAAAAAAAAAAAAAAAAAAA
题目名称	[NOIP 2010冲刺七]翻转游戏	最终得分	100
用户昵称	SOBER GOOD BOY	是否通过	通过
代码语言	C++	运行时间	0.230 s
提交时间	2016-08-02 13:52:01	内存使用	0.41 MiB

#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
//wuli 暴力搜索 
using namespace std;
 
const int Move[5][5]={{0,0},{0,-1},{0,1},{-1,0},{1,0}};
 
bool A[6][6];
 
bool flag[6][6];
 
int f[6][6][888];
int Ans=99999999;
void sou(int,int,int);
//b-> 0,w -> 1
int main()
{
	freopen("flip.in","r",stdin);
	freopen("flip.out","w",stdout);
	char ch;
	int tot=0;
	for(int i=1;i<=4;i++)
	{
		for(int j=1;j<=4;j++)
		{
			scanf(" %c",&ch);
			if(ch=='w')
			{
				A[i][j]=1;
				tot++;
			}
		}
	}
	if(tot==0||tot==16)
	{
		printf("0");
		return 0;
	}
	for(int i=1;i<=4;i++)
	{
		for(int j=1;j<=4;j++)
		{
			sou(i,j,1);
		}
	}
	if(Ans==99999999)printf("Impossible");
	else printf("%d",Ans);
 	fclose(stdin);
 	fclose(stdout);
 	return 0;
}
void sou(int x,int y,int step)
{
	if(f[x][y][step]>556)return;
	f[x][y][step]++;
	flag[x][y]=1;
	for(int i=0;i<5;i++)
	{
		int xx=x+Move[i][0],yy=y+Move[i][1];
		//if(xx<1||xx>4||yy<1||yy>4)continue;
		A[xx][yy]=!A[xx][yy];
	}
	int tot=0;
	for(int i=1;i<=4;i++)
	{
		for(int j=1;j<=4;j++)
		{
			tot+=A[i][j];
		}
	}
	if(tot==0||tot==16)
	{
		Ans=min(Ans,step);
		flag[x][y]=0;
		for(int i=0;i<5;i++)
	{
		int xx=x+Move[i][0],yy=y+Move[i][1];
		//if(xx<1||xx>4||yy<1||yy>4)continue;
		A[xx][yy]=!A[xx][yy];
	}
		return;
	}
	else
	{
		for(int i=1;i<=4;i++)
		{
			for(int j=1;j<=4;j++)
			{
				if(!flag[i][j])
				{
					sou(i,j,step+1);
				}
			}
		}
		flag[x][y]=0;
		for(int i=0;i<5;i++)
	{
		int xx=x+Move[i][0],yy=y+Move[i][1];
		//if(xx<1||xx>4||yy<1||yy>4)continue;
		A[xx][yy]=!A[xx][yy];
	}
	}
}