记录编号	43582	评测结果	AAAAAAAAAAAAAAAAAAAA
题目名称	[NOIP 2010冲刺七]翻转游戏	最终得分	100
用户昵称	苏轼	是否通过	通过
代码语言	C++	运行时间	0.083 s
提交时间	2012-10-11 19:34:48	内存使用	10.36 MiB

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
using namespace std;
struct hehe
{
    int w[5][5];
    int deep;
}q[70000];
int e[70000]={0};
int f[4][2]={{1,0},{0,1},{-1,0},{0,-1}};
void bfs()
{
    if (e[0]==(1<<16)-1||e[0]==0)
    {
        cout<<0;
        exit(0);
    }
    else
    {
        int tou,wei;
        tou=wei=0;
        while (tou<=wei)
        {
            if (wei>65536)
            {
                cout<<"Impossible";
                exit(0);
            }
            for (int i=0;i<4;i++)
            {
                for (int j=0;j<4;j++)
                {
                    int xx,yy;
                    q[wei+1]=q[tou];
                    q[wei+1].w[i][j]=1-q[tou].w[i][j];
                    for (int k=0;k<4;k++)
                    {
                        xx=i+f[k][0];
                        yy=j+f[k][1];
                        if (xx>=0&&xx<4&&yy>=0&&yy<4)
                        {
                            q[wei+1].w[xx][yy]=1-q[tou].w[xx][yy];
                        }
                    }
                    int tmp=0;
                    for (int k=0;k<4;k++)
                        for (int p=0;p<4;p++)
                            tmp=(tmp<<1)+(q[wei+1].w[k][p]);
                    bool temp=0;
                    if (tmp==(1<<16)-1||tmp==0)
                    {
                        cout<<q[tou].deep+1;
                        exit(0);
                    }
                    if (e[tmp])
                        temp=1;
                    if (!temp)
                    {
                        wei++;
                        e[tmp]=1;
                        q[wei].deep=q[tou].deep+1;
                    }
                }
            }
            tou++;
        }
    }
}
int main()
{
    freopen ("flip.in","r",stdin);
    freopen ("flip.out","w",stdout);
    for (int i=0;i<4;i++)
    {
        for (int j=0;j<4;j++)
        {
            char a;
            cin>>a;
            if (a=='w')
            {
                q[0].w[i][j]=0;
                e[0]=e[0]<<1;
            }
            if (a=='b')
            {
                q[0].w[i][j]=1;
                e[0]=e[0]<<1;
                e[0]=e[0]+1;
            }
        }
    }
	if (e[0]==(1<<16)-1||e[0]==0)
    {
        cout<<0;
        exit(0);
    }
    /*
    q[0].w[0][0]=1;
    q[0].w[0][1]=0;
    q[0].w[0][2]=1;
    q[0].w[0][3]=0;
    q[0].w[1][0]=0;
    q[0].w[1][1]=0;
    q[0].w[1][2]=0;
    q[0].w[1][3]=0;
    q[0].w[2][0]=1;
    q[0].w[2][1]=1;
    q[0].w[2][2]=0;
    q[0].w[2][3]=1;
    q[0].w[3][0]=1;
    q[0].w[3][1]=0;
    q[0].w[3][2]=0;
    q[0].w[3][3]=1;
    e[0]=41177;
    */
    q[0].deep=0;
    e[e[0]]=1;
    bfs();
    cout<<"Impossible";
    return 0;
}