Flip Game

题目

解题思路

1. 用二进制01串的思想来解，借助位运算。因为当第一行的按法确定之后，后面想要把所有棋都翻过来，最简按法是确定的。所以只要枚举第一行的按法就好了（0000~~1111）
2. 因为可以将白棋翻成黑棋，也可以黑翻白，所以定义了两个数组a（1表示黑）,b（1表示白）。

解题代码

#include<iostream>
using namespace std;
int a[10]={0},b[10]={0};
int cal(int x){//计算1的个数，也就是按了几下
	int cnt=0;
	while(x){
		if(x&1) cnt++;
		x=x>>1;
	}
	return cnt;
}
int deal(int a[]){
	int change[10],cnt=0;//change数组记录每一行的按法 
	int cur[10],ans=0x7f7f7f7f;//定义数组cur,表示a数组变成什么样了 
	for(change[0]=0;change[0]<=(1<<4)-1;change[0]++){//枚举第一行有多少种按法 
		cnt=cal(change[0]);
		cur[0]=a[0]^change[0]^(change[0]>>1)^((change[0]<<1)&(1<<4)-1);//第一行按完之后的样子 
		cur[1]=a[1]^change[0];//下一行受到的影响 
		for(int i=1;i<=3;i++){
			change[i]=cur[i-1];//记录第i行要怎么按 
			cnt+=cal(change[i]);
			cur[i]=cur[i]^change[i]^(change[i]>>1)^((change[i]<<1)&(1<<4)-1);//第i行按完后的样子 
			cur[i+1]=a[i+1]^change[i];//下一行受到的影响 
		}
		if(cur[3]==0) ans=min(ans,cnt);
	}
	return ans;
}
int main(){
	for(int i=0;i<=3;i++){
		for(int j=0;j<4;j++){
			char c;
			cin>>c;
			if(c=='b') a[i]=a[i] | (1<<j);//把j+1位变成1
			if(c=='w') b[i]=b[i] | (1<<j);
		}
	}
	int k=deal(a);
	int t=deal(b);
	int ans=min(k,t);//两种翻法取简单的
	if(ans==0x7f7f7f7f) cout<<"Impossible\n";
	else cout<<ans<<endl;
	return 0;
}

位运算知识点

• 与运算 & ：只有两个都是1的情况下结果=1，否则=0
• 或运算 | ：只要其中一个等于1结果=1，否则=0
• 异或运算 ^ ：两者不一样结果=1，否则=0
• (1<<4)-1 :1左移四位10000 然后减一 1111