#include <iostream>
using namespace std;

int fanzhuan[16];
int mychess;
char chess[18];
//翻转第i个，利用了按位异或，与1异或相当于翻转，与0异或相当于不转
int turn[16] = {0xC800,0xE400,0x7200,0x3100,0x8C80,0x4E40,0x2720,0x1310,0x08C8,0x04E4,0x0272,0x0131,0x008C,0x004E,0x0027,0x0013};

//我是核心部分哦~
bool dfs(int now,int level,int last )//从last开始
{
	if(now==level)//现在已经是第level次翻转了
	{
		if(mychess==0||mychess==0x00ffff)
			return true;
		else
			return false;
	}else{
		//还剩16-last个可供翻转，但是我还想要翻转level-now个
		if(16-last<level-now)
			return false;
		for(int i =last;i<16;i++)
		{
			if(fanzhuan[i])//已经翻转过了，没必要再翻转了
				continue;

			fanzhuan[i]=1;//翻转i
			mychess^=turn[i];
			
			if(dfs(now+1,level,i))//如果我把第i个翻转后，继续进行会成功，那么返回true。如果将来不成功，再把i转回来
				return true;
			
			fanzhuan[i]= 0;//既然不成功，转回来呗
			mychess^=turn[i];
		}
	return false;
	}
}

int main()
{
	int i=0;
	//输入字符
	while(i<16)
	{
		cin>>chess+i;
		i+=4;
	}
	//将字母转化为数字
	mychess =0;
	for(i=0;i<16;i++)
	{
		if(chess[i]=='b')//b->1
			mychess |=(1<<(15-i));
	}
	if(mychess!=0&&mychess!=0xffff)
	{
		for(i=1;i<=16;i++)
		{
			//选取i个翻转
			memset(fanzhuan,0,sizeof(fanzhuan));
			if(dfs(0,i,0))
				break;
		}
		if(i>16)
			printf("Impossible\n");
		else
			printf("%d\n",i);
	}else
	{
		printf("0\n");
	}
	cin>>i;
	return 0;
}

• Re:位运算16MS (1481) xiaogaga 2013-05-07 16:26:45