1168: PIPI的方格

2^n

#include <bits/stdc++.h>
using namespace std;
int main(){int n;while(scanf("%d",&n)!=EOF){int a[18][18];	//涴欴扂憩衄峈0腔padding賸 memset(a,0,sizeof(a));int sum1=0;for(int i=1;i<=n;i++){for(int j=1;j<=n;j++){scanf("%d",&a[i][j]);sum1+=a[i][j];}}int tp= 1<<n;int ans=15*15+10;for(int i=0;i<tp;i++){bool flag=0;int b[18][18];int sum2=0;memset(b,0,sizeof(b));for(int k=0;k<n;k++){if(i&(1<<k)){b[1][k+1]=1;}else{b[1][k+1]=0;if(b[1][k+1]==0&&a[1][k+1]==1){flag =1;break;}}sum2+=b[1][k+1];}if(flag) continue;for(int j=2;j<=n;j++){for(int m=1;m<=n;m++){b[j][m]=(b[j-2][m]+b[j-1][m-1]+b[j-1][m+1])%2;if(b[j][m]==0&&a[j][m]==1){flag =1;break;}sum2+=b[j][m];}if(flag)break;}
;if(flag)continue;if(sum2-sum1<ans){ans=sum2-sum1;}}if(ans==15*15+10)printf("-1\n");elseprintf("%d\n",ans);}return 0;
}