记录编号	43414	评测结果	AAAAAAAAAAAAAAAAAAAA
题目名称	[NOIP 2010冲刺七]翻转游戏	最终得分	100
用户昵称	TBK	是否通过	通过
代码语言	C++	运行时间	2.968 s
提交时间	2012-10-10 13:39:29	内存使用	2.99 MiB

#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;
}