学步园

Description

Input

Output

Sample Input

bwwb
bbwb
bwwb
bwww

Sample Output

4

Source

Northeastern Europe 2000

解题思路：枚举所有状态，每个棋子有翻或不翻，因为要求最少翻动次数，所以每个棋子翻动奇数次等价于翻动1次，翻动偶数次等价于不翻，一共有2^16个状态，我用的是DFS，每次判断是否超出枚举范围，超出则枚举范围扩大一次，否则判断是否达到目标（定义一个函数扫描棋盘上是否有子不等于（1,1）位置的子，有则返回false,否则返回true）达到目标则搜索结束，否则搜索下一粒子的位置，直至达到本次枚举范围，网上大牛有用16进制表示棋盘状态来做的，代码也一并附上。

#include<iostream>
using namespace std;
char chess[6][6]={'*'};
bool Chess[6][6]={0};
bool finish()//判断是否全黑或全白
{
	int i,j;
	for(i=1;i<=4;i++)
		for(j=1;j<=4;j++)
			if(Chess[i][j]!=Chess[1][1])
				return false;
	return true;
}
void flip(int m,int n)//翻棋操作
{
	Chess[m][n]=!Chess[m][n];
	Chess[m-1][n]=!Chess[m-1][n];
	Chess[m+1][n]=!Chess[m+1][n];
	Chess[m][n+1]=!Chess[m][n+1];
	Chess[m][n-1]=!Chess[m][n-1];
}
bool dfs(int x,int y,int now,int deep)
{
	if(now>deep)   return false;//判断是否超出枚举范围
	if(finish())   return true;
	for(int i=x;i<=4;i++)
		for(int j=y;j<=4;j++)
		{
			flip(i,j);//翻棋
			if(j<4)//同一行的没翻完继续翻，翻完就翻下一行
			{if(dfs(i,j+1,now+1,deep))  return true;}//同一行
			else
			{if(dfs(i+1,1,now+1,deep))  return true;}//下一行
			flip(i,j);//不成功则翻回最后一粒子重新搜索下一个目标位
			if(j==4)//如果一列翻完且搜索失败，下一轮翻棋重新由下一行第一列开始
				y=1;
		}
	return false;
}
int main()
{
	int i,j,step;
	bool flag=false;
	for(i=1;i<=4;i++)
		for(j=1;j<=4;j++)
			{
				cin>>chess[i][j];
				if(chess[i][j]=='b')
					Chess[i][j]=1;
		    }
	for(step=0;step<=16;step++)//状态总共2^16种，即翻棋有翻0,1,2.....16粒子，共17种选择
		if(dfs(1,1,0,step))
		{
			flag=true;
			break;
		}
		if(flag)
			cout<<step<<endl;
		else
			cout<<"Impossible\n";
	return 0;
}

//大牛的十六进制表示法：

/*代码二：BFS+Bit*/

//把矩阵看成一个16进制数
//每一行代表16进制数的一个字母（或数字），而每一个字母（或数字）又恰由4个二进制位数字0和1组成
//因此一个4x4矩阵是由16位0和1构成，是从 第0位 到 第15位
//如矩阵  

//        * * * *      从右到左分别为第 0, 1, 2, 3位
//        % % % %      从右到左分别为第 4, 5, 6, 7位
//        # # # #      从右到左分别为第 8, 9,10,11位
//        @ @ @ @      从右到左分别为第12,13,14,15位

//代表16进制数  

//   @@@@ #### %%%% ****
//  15      ←         0

//   将一个int的某位 取反 用该int与(0x1<<i)进行^操作。
  


#include<iostream> 

struct unit
{ 
	int x;   //用int的末16位记录16个位置的信息
	int rounds;   //记录第几轮达到当前的状态
	int i;   //记录该状态是通过翻动哪个棋子得来的，以避免返回先前的状态
}; 


//flip函数是从a状态通过翻动第i个棋子到达b状态

void flip(unit a, int i, unit& b)   //a是queue[p]的形参, 当前要翻动第i只棋子, b是queue[q]的引用
{ 
	int x = i / 4, y = i % 4;   //x、y为当前要翻动的第i只棋子所对应内节点的坐标（就是所翻动棋子的行x列y）
	b.x = a.x;      //即令queue[q].x=queue[p].x  ,即q先复制p（前一步）的状态，再对q进行翻转（对p状态无影响）
	b.x = ((b.x) ^ (0x1 << (i)));    //将一个b.x的第i位 取反，其实就是把 第i只棋子 翻转
	if (x > 0) 
		b.x = ((b.x) ^ (0x1 << (i - 4)));  //把 第i只棋子 上面的棋子翻转，当且仅当棋子i不在第0行时执行
	if (x < 3) 
		b.x = ((b.x) ^ (0x1 << (i + 4)));  //把 第i只棋子 下面的棋子翻转，当且仅当棋子i不在第3行时执行
	if (y > 0) 
		b.x = ((b.x) ^ (0x1 << (i - 1)));  //把 第i只棋子 右面的棋子翻转，当且仅当棋子i不在第0列时执行
	if (y < 3) 
		b.x = ((b.x) ^ (0x1 << (i + 1)));  //把 第i只棋子 左面的棋子翻转，当且仅当棋子i不在第3列时执行
	b.rounds = a.rounds + 1;   //当前执行翻转棋子的次数
	b.i = i; //记录当前翻转的是第i只棋子
	return;
} 

int main() 
{ 
	/*queue*/ 
	unit queue[100000];     //queue是一个队列，记录所有状态
	queue[0].x = 0;   //初始化为16进制的0（16进制的0和10进制的0是一样的）
	queue[0].i = -1; 
	queue[0].rounds = 0; 
	
	//judge used 
	bool used[100000]={false};    //used记录已经存在的状态
	/*read in*/ 
	char str[10]; 
	for (int i = 0; i < 4; i++) 
	{ 
		scanf("%s", str);  //一次输入一行字符串str（串长为4），输4次
		for (int j = 0; j < 4; j++)
			if (str[j] == 'b')  
				queue[0].x = ((0x1 << (i * 4 + j)) | (queue[0].x));  //位运算，遇b该位置1
	}                     // 0x1为16进制的1

	int p = 0, q = 0;     //p，q分别是队列的头尾指针

	//其实queue[p].x代表每一步的翻转前状态，queue[q].x代表每一步的翻转后状态

	while (!((queue[q].x == 0) || (queue[q].x == 0xFFFF)))      //当16进制数queue[q].x 不为0（全0）或15（全1）时执行
	{ 
		for (int i = 0; i < 16; i++)   //最多翻动16只棋子，i代表第i只棋子
		{ 
			if(queue[p].i==i)   //若翻动当前棋子i的前一步所翻的棋子queue[p].i就是i，则跳过不翻动
				continue; 
			q++;   //尾指针后移一位，为新状态“开辟”新的记录空间
			flip(queue[p], i, queue[q]); 
			if (used[queue[q].x])  //以棋盘的状态（一个16进制数）作为数组used的下标，对应的对象为true时说明这个状态已经出现过
				q--;               //在得到一个新状态的时候要检验之前时候存在这个状态，如果存在就把这个状态舍弃，即q--  
			                        //但是下一次循环则继续翻下一只棋子，与状态的舍弃无关，相当于本次所翻的棋子操作无效
			else
				used[queue[q].x]=true; //若该状态没有出现过，则记录该状态
			if ((queue[q].x == 0) || (queue[q].x == 0xFFFF))break; //棋盘状态为全0或全1时跳出for，由于while的条件关系，自然也跳出while
		} 

		if (p==q) //此条件为真时，当且仅当BFS到最后一层的最后一种状态时仍没有匹配的状态（全0或全1）
		{         //简单来说，就是当搜索到最后一层时，程序通过条件结束for,而不是通过break
			printf("Impossible");    //直至搜索结束，队列queue中都没有目标状态（此时为impossible）。 
			break; 
		} 

		p++; //头指针后移一位，把当前状态作为初始状态
	} 
	if ((queue[q].x == 0) || (queue[q].x == 0xFFFF))   //这是为了隔离因"impossible"时跳出while的情况
		printf("%d\n", queue[q].rounds); 
	return 0; 
}