现在的位置: 首页 > 综合 > 正文

POJ Flip Game

2013年08月26日 ⁄ 综合 ⁄ 共 892字 ⁄ 字号 评论关闭
//枚举题
//由于总共有2的16次方个动作,动作的意思就是如果该数的某位为1的话,就进行抑或操作
//改变每一位对应的操作是与相应的数字进行抑或,我们用oper数组定义
#include<iostream>
using namespace std;

int mat[4][4];
int oper[16]={
	0xC800,0xE400,0x7200,0x3100,
	0x8C80,0x4E40,0x2720,0x1310,
	0x08C8,0x04E4,0x0272,0x0131,
	0x008C,0x004E,0x0027,0x0013
};
int comp[16];
int res,ans;
void putin(int a){
	int num=15;
	while(a){
		comp[num]=a%2;
		a=a/2;
		num--;
	}
}
int numof(){
	int sum=0;
	for(int i=0;i<16;i++){
		if(comp[i]==1)
			sum++;
	}
	return sum;
}
int main()
{
	char ch;
	res=0;
	for(int i=0;i<4;i++){
		for(int j=0;j<4;j++){
			scanf("%c",&ch);
			if(ch=='b'){
				mat[i][j]=1;
				res+=1<<(15-(4*i+j));//一开始错误的原因是把1写成2了,1左移等于2的多少次方,要记清楚。
			}else{
				mat[i][j]=0;
			}
		}
		getchar();
	}
	int tmp,max;
	ans=16;
	bool flag=false;
	for(int i=0;i<65536;i++){
		tmp=res;
		memset(comp,0,sizeof(comp));
		putin(i);
		for(int j=0;j<16;j++){
			if(comp[j]==1){
				tmp=tmp^oper[j];
			}
		}
		if(tmp==0||tmp==65535){
			flag=true;
			max=numof();
			if(ans>max)
				ans=max;
		}
	}
	if(flag)
		printf("%d\n",ans);
	else
		printf("Impossible\n");
	return 0;
}
【上篇】
【下篇】

抱歉!评论已关闭.