#include <cstdio>
#include <cstring>
#include <iostream>
using namespace std;
int a[5][5],x;

struct poj
{
	int num;
	long long step;
}q[100005];
bool ans[70000];

int get_num(int x,int k1,int k2)
{
	int a[5][5],w=0;
	memset(a,0,sizeof(a));
	for(int i=1;i<=4;i++)
		for(int j=1;j<=4;j++)
		{
			a[i][j]=x%2;
			x/=2;
		}
	a[k1][k2]=1-a[k1][k2];
	if(k2-1>0)a[k1][k2-1]=1-a[k1][k2-1];
	if(k2+1<5)a[k1][k2+1]=1-a[k1][k2+1];
	if(k1-1>0)a[k1-1][k2]=1-a[k1-1][k2];
	if(k1+1<5)a[k1+1][k2]=1-a[k1+1][k2];
	int y=0;
	for(int i=1;i<=4;i++)
		for(int j=1;j<=4;j++)
			y+=a[i][j]<<((i-1)*4+j)-1;
	return y;
}

long long bfs()
{
	if(x==0 || x==65535)return 0;
	memset(ans,0,sizeof(ans));
	int l,r,tmp;
	l=r=1;q[l].num=x;q[l].step=0;
	while(l<=r)
	{
		for(int i=1;i<=4;i++)
		{
			for(int j=1;j<=4;j++)
			{
				tmp=get_num(q[l].num,i,j);
				if(!ans[tmp])
				{
					ans[tmp]=1;
					if(tmp==0 || tmp==65535)return q[l].step+1;
					r++;
					q[r].num=tmp;
					q[r].step=q[l].step+1;
				}
			}
		}
		l++;
	}
	return -1;
}

int main()
{
	char c;
	for(int i=1;i<=4;i++)
		for(int j=1;j<=4;j++)
		{
			cin>>c;
			if(c=='b')a[i][j]=0;
			else a[i][j]=1;
		}
	for(int i=1;i<=4;i++)
		for(int j=1;j<=4;j++)
			x+=a[i][j]<<((i-1)*4+j)-1;
	long long ans=bfs();
	if(ans<0)printf("Impossible\n");
	else printf("%I64d\n",ans);
	return 0;
}

• Re:bfs~~用位运算压缩，附代码 (974) y0h123 2018-12-17 20:14:00
• Re:bfs~~用位运算压缩，附代码 (974) y0h123 2018-12-17 20:14:01