传送门
这是我第2次遇到相同类型的题目了。
如果暴力搜索时间复杂度是指数的指数。
但这类题目有个特点就是可以通过已有的条件推出其他的解（我们可以从第一行排列进而完全推出第二行，然后第三行。。。）
思路：枚举第一行的状态（用01枚举子集）时间复杂度O(2n)
然后计算2~n行状态，这样总的时间复杂度为：O（n2∗2n）
code:
#include<bits/stdc++.h>
using namespace std;
const int N=20;
const int inf=0x3f3f3f;
int n,a[N][N],b[N][N];
int check(int s){
memset(b,0,sizeof(b));
for(int c=0;c<n;c++){
if(s&(1<<c)) b[0][c]=1;
else if(a[0][c]==1) return inf;
}
for(int r=0;r<n-1;r++)
for(int c=0;c<n;c++){
int sum=0;
if(r>0) sum+=b[r-1][c];
if(c>0) sum+=b[r][c-1];
if(c<n-1) sum+=b[r][c+1];
b[r+1][c]=sum%2;
if(a[r+1][c]==1&&b[r+1][c]==0) return inf;
}
int cnt=0;
for(int r=0;r<n;r++)
for(int c=0;c<n;c++) if(a[r][c]!=b[r][c]) cnt++;
return cnt;
}
int main(){
int T;
cin>>T;
for(int kase=1;kase<=T;kase++){
cin>>n;
for(int r=0;r<n;r++)
for(int c=0;c<n;c++) cin>>a[r][c];
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);
}
}