学步园

#include <iostream>
#include <queue>
using namespace std;
const int ALLBLACK=65535;
const int ALLWHITE=0;
const int MAX=65536;
int convert(char c){
	if('b'==c)
		return 1;
	if('w'==c)
		return 0;
}
/**
   为了提高搜索效率,采用位运算,
   如果想将整数的二进制某一位翻转可采用
   id^=(1<<x)(x代表要翻转的位置)
  */
int flipgame(int statenum,int pos){//转换
	statenum^=(1<<pos);//当前位翻转
	if(pos/4>0)//up
		statenum^=(1<<(pos-4));
	if(pos/4<3)//down
		statenum^=(1<<(pos+4));
	if(pos%4>0)//left
		statenum^=(1<<(pos-1));
	if(pos%4<3)
		statenum^=(1<<(pos+1));
	return statenum;
}
int main(){
	char c;
	int i,statenum=0;
	for(i=0;i<16;i++){//初始化状态
		cin>>c;
		statenum+=(convert(c)<<i);
	}
	if(ALLBLACK==statenum||ALLWHITE==statenum)
	{
		cout<<0<<endl;
		return 0;
	}
	int state[65536];//记录从初始态达到某个状态所需的步数
	memset(state,-1,sizeof(state));
	queue<int> q;
	int nextnum;
       state[statenum]=0;
	q.push(statenum);
	//求解释
	while(!q.empty()){
		statenum=q.front();
		q.pop();
		for(i=0;i<16;i++){
			nextnum=flipgame(statenum,i);
				if(ALLBLACK==nextnum||ALLWHITE==nextnum)
				{
					cout<<state[statenum]+1<<endl;
						return 0;
				}
				if(state[nextnum]==-1){
					state[nextnum]=state[statenum]+1;
					q.push(nextnum);
				}
		}
	}
	cout<<"Impossible"<<endl;
	return 0;
}