比赛 20121009 评测结果 AAAAAAAAAAAAAAAAAAAA
题目名称 翻转游戏 最终得分 100
用户昵称 TBK 运行时间 2.978 s
代码语言 C++ 内存使用 3.15 MiB
提交时间 2012-10-09 21:02:22
显示代码纯文本
#include <iostream>
#include <cstring>
#include <cstdlib>
#include <cstdio>
#include <cmath>
#include <string>
#include <set>
#include <vector>
#include <algorithm>
using namespace std;
int a,b,c,d;
bool bo[4][4],boo[4][4],booo[4][4],ob;
char ch;
void check(void)
{
	int i,j,k;
	k=bo[0][0];
	for (i=0;i<4;i++)
	{
		for (j=0;j<4;j++)
			if (bo[i][j]!=k) break;
		if (j!=4) break;
	}
	if (i==4&&j==4) ob=true;
}
void gaibian(int i,int j)
{
	bo[i][j]=!bo[i][j];
	if (i-1>=0) bo[i-1][j]=!bo[i-1][j];
	if (i+1<=3) bo[i+1][j]=!bo[i+1][j];
	if (j-1>=0) bo[i][j-1]=!bo[i][j-1];
	if (j+1<=3) bo[i][j+1]=!bo[i][j+1];
}
void DFS(int x)
{
	int i,j;
	if (x==a)
	{
		check();
		if (ob==true)
		{
			printf("%d",a);
			exit(0);
		}
		return ;
	}
	for (i=0;i<4;i++)
		for (j=0;j<4;j++)
			if (booo[i][j]==false)
			{
				booo[i][j]=true;
				gaibian(i,j);
				DFS(x+1);
				gaibian(i,j);
				booo[i][j]=false;
			}
}
int main(void)
{
	freopen ("flip.in","r",stdin);
	freopen ("flip.out","w",stdout);
	for (a=0;a<4;a++)
		for (b=0;b<4;b++)
		{
			cin>>ch;
			if (ch=='b') c=0;
				else c=1;
			bo[a][b]=c;
		}
	check();
	if (ob==true) 
	{
		printf("0");
		return 0;
	}
	for (a=1;a<=6;a++) DFS(0);
	printf("Impossible");
	fclose(stdin);
	fclose(stdout);
	return 0;
}