位运算枚举矩阵的所有状态，和输入的矩阵比较，一旦发现枚举的矩阵元素是0，而输入的矩阵对应元素是1（因为1不能不能变成0），就跳出，直到找到为止
#include <iostream> #include <cstring> #include <cstdio> #include <algorithm> using namespace std; const int maxn=20; int a[maxn][maxn],t,n,b[maxn][maxn]; const int inf=0x3f3f3f3f; int judge(int x) { memset(b,0,sizeof(b)); for(int i=0;i<n;i++) { if(x&(1<<i)) b[1][i+1]=1; else { if(a[1][i+1]==1) { return inf; } } } int l,r,u,d; for(int i=1;i<n;i++) { for(int j=1;j<=n;j++) { if(j-1==0) l=0;//左 else l=b[i][j-1]; if(j+1>n) r=0;//右 else r=b[i][j+1]; if(i-1==0) u=0;//上 else u=b[i-1][j]; if(i+1>n) d=0;//下，注意这里是找a的下 else d=a[i+1][j]; int dd=(l+r+u)%2; if(dd==0&&d==1) return inf; b[i+1][j]=dd; } } int sum=0; for(int i=1;i<=n;i++) for(int j=1;j<=n;j++) if(a[i][j]!=b[i][j]) sum++; return sum; } int main() { scanf("%d",&t); for(int zz=1;zz<=t;zz++) { int ans=inf; scanf("%d",&n); for(int i=1;i<=n;i++) for(int j=1;j<=n;j++) scanf("%d",&a[i][j]); int flag=0; for(int i=0;i<(1<<n);i++) ans=min(ans,judge(i)); printf("Case %d: ",zz); if(ans==inf) printf("-1\n"); else printf("%d\n",ans); } return 0; }
转载于:https://www.cnblogs.com/Wangwanxiang/p/7421906.html
