思路：
只需要枚举第一列，后面的每一列根据前面的列来看是否需要flip
要枚举第一列的那些行需要flip，哪些不需要flip，不可能写4个for循环
- 我们采用二进制枚举（状压），例如1010表示第一行和第3行要flip.
- 第二列的的某一行flip了对于第一列，只会影响同行的第一列， 所以第二列的是否要flip就要看第一列的哪些行有不符合目标，其余列以此类推
- 这里可以全部是黑色也可以全部是白色，所以我们都计算取最小值。 下面的代码看懂了黑色怎么处理就懂了白色，所以读者看一种即可
AC代码：
#include<iostream>
#include<cstdlib>
#include<algorithm>
#include<cstring>
using namespace std;
const int maxn = 10;
char s[maxn][maxn];
int ans =1e9;
//每次翻转完后检查
int check(int b[maxn][maxn],int x)
{
for(int i=1;i<=4;i++)
{
for(int j=1;j<=4;j++)
{
if(b[i][j]==x) return 0;
//printf("%d",b[i][j]);
}
//printf("\n");
}
return 1;
}
void allb()//1代表黑色
{
for(int i=0;i<=15;i++)
{
int b[maxn] ;//代表第一列的翻转状态,1代表翻转，0代表不反转
int n = 4;
int x = i;
//转为二进制
int cnt = 0;
while(n)
{
b[n--]=x&1;
x>>=1;
}
//赋值
int bi[maxn][maxn];
memset(bi,0,sizeof(bi));
for(int j=1;j<=4;j++)
{
for(int k=1;k<=4;k++)
{
if(s[j][k]=='b') bi[j][k] = 1;
}
}
//处理第一列
for(int r=1;r<=4;r++)
{
if(b[r])
{
cnt++;
bi[r][1]=!bi[r][1]; //自己
bi[r][2]=!bi[r][2];//右
bi[r-1][1]=!bi[r-1][1];//上
bi[r+1][1]=!bi[r+1][1];//下
}
}
//第二--四例
for(int c=2;c<=4;c++)//枚举列
{
for(int r=1;r<=4;r++)
{
if(!bi[r][c-1])
{
cnt++;
bi[r][c]=!bi[r][c]; //自己
bi[r-1][c]=! bi[r-1][c];//上
bi[r+1][c]=! bi[r+1][c];//下
bi[r][c-1]=! bi[r][c-1];//左
bi[r][c+1]=!bi[r][c+1];//右
}
}
}
if(check(bi,0))
{
ans=min(ans,cnt);
}
}
}
void allw()//0代表白色
{
for(int i=0;i<=15;i++)
{
int b[maxn] ;//代表第一列的翻转状态
int n = 4;
int x = i;
//转为二进制
int cnt = 0;
while(n)
{
b[n--]=x&1;
x>>=1;
}
//赋值
int bi[maxn][maxn];
memset(bi,0,sizeof(bi));
for(int j=1;j<=4;j++)
{
for(int k=1;k<=4;k++)
{
if(s[j][k]=='b') bi[j][k] = 1;
}
}
//处理第一列
for(int r=1;r<=4;r++)
{
if(b[r])
{
cnt++;
bi[r][1]=!bi[r][1]; //自己
bi[r][2]=!bi[r][2];//右
bi[r-1][1]=! bi[r-1][1];//上
bi[r+1][1]=! bi[r+1][1];//下
}
}
//第二--四例
for(int c=2;c<=4;c++)//枚举列
{
for(int r=1;r<=4;r++)
{
if(bi[r][c-1])
{
cnt++;
bi[r][c]=!bi[r][c]; //自己
bi[r-1][c]=! bi[r-1][c];//上
bi[r+1][c]=! bi[r+1][c];//下
bi[r][c-1]=! bi[r][c-1];//左
bi[r][c+1]=!bi[r][c+1];//右
}
}
}
if(check(bi,1))
{
ans=min(ans,cnt);
}
}
}
int main()
{
for(int i=1;i<=4;i++)
{
for(int j=1;j<=4;j++)
{
cin>>s[i][j];
}
}
allb();
allw();
if(ans==1e9) printf("Impossible\n");
else cout<<ans<<endl;
return 0;
}
京公网安备 11010502036488号