思路：**枚举第一行的所有情况**（因为只看上下左右，所以第一行确定后，就可以确定剩余行的情况了QwQ）
这里我们**采用x状压一下**，然后从小到达枚举x（即枚举把第一行的哪些0变成1），把修改过第一行的原数组存到b数组中（ps：要判断**有没有把1改成0**，改了则不行，跳过）。
然后根据第一行确定要变化其他行的哪些数字，如果**存在需要把1改成0的情况，则此方案不行。**
最后取每种情况的最小值就好啦~ 附上本蒟蒻的代码QWQ
```cpp
#include<bits/stdc++.h>
using namespace std;
int t,n,x,ans;
int a[20][20],b[20][20];//b存每种情况修改后的数组
int dx[3]={0,0,-1};
int dy[3]={1,-1,0};//上左右三个方向
int check(int m){//当第一行的情况为m时
int num=0;//需要修改的次数
for(int i=n;i>=1;i--){
b[1][i]=m&1;
m=m>>1;
if(a[1][i]==0&&b[1][i]==1)
num++;
if(a[1][i]==1&&b[1][i]==0)//如果把1变为0了
return 0x7fffffff;//此方案不行
}
for(int i=1;i<n;i++){
for(int j=1;j<=n;j++){
int sum=0;
for(int k=0;k<3;k++){
int xx=dx[k]+i;
int yy=dy[k]+j;
if(xx>0&&xx<=n&&yy>0&&yy<=n)
sum+=b[xx][yy];
}
if(sum%2==0&&b[i+1][j]==1) return 0x7fffffff;//三个方向
和为偶数，下方数为0，不行
if(sum%2==1&&b[i+1][j]==0) b[i+1][j]=1,num++;//0改1
}
}
return num;
}
int main(){
scanf("%d",&t);
for(int cas=1;cas<=t;cas++){
ans=0x7fffffff;
scanf("%d",&n);
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)
scanf("%d",&a[i][j]);
for(int i=1;i<=n;i++)
x+=x<<2+a[1][i];
for(int i=x;i<(1<<n);i++){//枚举第一行
for(int xx=1;xx<=n;xx++)
for(int yy=1;yy<=n;yy++)
b[xx][yy]=a[xx][yy];
ans=min(ans,check(i));
}
if(ans==0x7fffffff) printf("Case %d: -1\n",cas);
else printf("Case %d: %d\n",cas,ans);
}
return 0;
}
```
原文：https://www.cnblogs.com/Johanna/p/12101284.html