题目链接：https://vjudge.net/problem/UVA-11464
一道比较好的题目。
思路如下：
如果我们枚举每一个数字“变”还是“不变”，那么需要枚举$2^{255}$种情况，很显然不行。
那么我们就来优化一下：我们只枚举第一行的数，然后根据计算得出第二、三....行的数。
这样复杂度就优化到了$O(2^n\times n^2)$。
然后用$A[][]$和$B[][]$分别表示变化前后的矩阵。
那么现在的问题就简化成了如何枚举第一行和如何递推。
枚举第一行：运用了状压的思想，把一行数看成一个二进制数，然后$&(1<<c)$，看是否为1，由此我们就构造了一个如下图所示的矩阵。
递推方法：
求出$B[r-1][c]$的上、左、右数之和，如果为偶数，则$B[r][c]=0$，反之$B[r][c]=1$。
在递推中如果发现由$1$转变到$0$的情况，那么是不可能的。
AC代码：
#include<cstdio>
#include<iostream>
#include<cstring> using namespace std; const int maxn=;
const int INF=0x7f7f7f;
int n,A[maxn][maxn],B[maxn][maxn]; int check(int s){
memset(B,,sizeof(B));
for(int c=;c<n;c++){
if(s&(<<c)) B[][c]=;
else if(A[][c]==) return INF;
}
for(int r=;r<n;r++){
for(int c=;c<n;c++){
int sum=;
if(r>) sum+=B[r-][c];
if(c>) sum+=B[r-][c-];
if(c<n-) sum+=B[r-][c+];
B[r][c]=sum%;
if(A[r][c]==&&B[r][c]==) return INF;
}
}
int cnt=;
for(int r=;r<n;r++)
for(int c=;c<n;c++) if(A[r][c]!=B[r][c]) cnt++;
return cnt;
} int main(){
int T;
scanf("%d",&T);
for(int k=;k<=T;k++){
scanf("%d",&n);
for(int r=;r<n;r++)
for(int c=;c<n;c++) scanf("%d",&A[r][c]);
int ans=INF;
for(int s=;s<(<<n);s++)
ans=min(ans,check(s));
if(ans==INF) ans=-;
printf("Case %d: %d\n",k,ans);
}
return ;
}
AC代码