比赛 |
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;
}