poj 1753 Flip Game

#include <stdio.h>
#include <string.h>
#include <math.h>

char map[6][6],copy[6][6],str[20];
const int INF=666;
int ans;
int flag[6][6];

bool Check(char copy[][6]){//检查所有棋子是不是都是一样的颜色 
	
	char ch=copy[0][0];
	for(int i=0;i<4;i++)
		for(int j=0;j<4;j++)
			if(copy[i][j]!=ch)
				return false;
	return true;
}

void Change(int i,int j){//棋子颜色的翻转 
	copy[i][j]=(char)(‘b‘+‘w‘-copy[i][j]);
	if(i!=0)
		copy[i-1][j]=(char)(‘b‘+‘w‘-copy[i-1][j]);
	if(j!=0)
		copy[i][j-1]=(char)(‘b‘+‘w‘-copy[i][j-1]);
	if(i!=3)
		copy[i+1][j]=(char)(‘b‘+‘w‘-copy[i+1][j]);
	if(j!=3)
		copy[i][j+1]=(char)(‘b‘+‘w‘-copy[i][j+1]);
}

void BFS(){//暴力搜索加位运算 
	
	if(Check(map))//若是本身就已经是满足的情况，就不必翻转 
		ans=0;		
	else
		for(int t=1;t<65536;t++){//枚举所有的翻转情况，并且分析 
			int num=t;
			int step=0;
			for(int coi=0;coi<4;coi++)
				for(int coj=0;coj<4;coj++)
					copy[coi][coj]=map[coi][coj];//复制棋子图 
			for(int i=0;i<4;i++)
				for(int j=0;j<4;j++){
					flag[i][j]=num%2;//利用位运算进行分析 
					num/=2;
					if(flag[i][j]==1){//1要变，0保持原状 
						Change(i,j);
						step++;	//记录变化的次数 
					}
				}
			if(Check(copy))//当期棋子图满足要求 
				ans=ans<step?ans:step;//及时更新最小的变化次数 
		}
}

int main(){
	
	for(int i=0;i<4;i++)
		gets(map[i]);
	ans=INF;
	BFS();//主要搜索函数 
	if(INF!=ans)//若是没有一种情况满足，ans为初值INF 
		printf("%d\n",ans);
	else
		puts("Impossible");
	return 0;
}

poj 1753 Flip Game

原文：http://www.cnblogs.com/huaixiaohai2015/p/5168698.html