分析
标准的套路题。
枚举第一行，接着根据第一行递推下面的行。
时间复杂度$ O(2^n \times n^2) $
代码
#include <bits/stdc++.h> using namespace std; const int maxn=20, INF=1e9; int A[maxn][maxn], n, B[maxn][maxn]; int check(int s){ int ans=0; memset(B,0,sizeof(B)); for(int i=0;i<n;i++) if(s&(1<<i)) B[1][i+1]=1; else if(A[1][i+1]==1) return INF; for(int i=1;i<n;i++){ for(int j=1;j<=n;j++){ int sum=B[i][j+1]+B[i][j-1]+B[i-1][j]; B[i+1][j]=sum%2; if(A[i+1][j]==1&&B[i+1][j]==0) return INF; } } for(int i=1;i<=n;i++) for(int j=1;j<=n;j++){ if(A[i][j]!=B[i][j]) ans++; } return ans; } int main(){ int T; scanf("%d",&T); for(int kase=1;kase<=T;kase++){ scanf("%d",&n); for(int i=1;i<=n;i++) for(int j=1;j<=n;j++) scanf("%d",&A[i][j]); int ans=INF; for(int s=0;s<(1<<n);s++){ ans=min(ans,check(s)); } if(ans == INF) ans = -1; printf("Case %d: %d\n", kase, ans); } return 0; }