偶数矩阵 Even Parity,UVa 11464

 1 #include <stdio.h>
 2 #include <stdlib.h>
 3 #include <string.h>
 4 #include <math.h>
 5 const int MAXN=20;
 6 const int INF=100000;
 7 int A[MAXN][MAXN],B[MAXN][MAXN];
 8 int n;
 9 int min(int a,int b)
10 {
11     return a>b?b:a;
12 }
13 int check(int s)
14 {
15     memset(B,0,sizeof(int));
16     for(int c=0;c<n;c++)//枚举第一行 
17     {
18         if(s&(1<<c)) B[0][c]=1;
19         else if(A[0][c]==1) return INF;//不能把1变成0，直接返回 
20     }
21     for(int r=1;r<n;r++)//从第二行开始依次筛查 
22     {
23         for(int c=0;c<n;c++)
24         {
25             int sum=0;//表示上左右三个元素的和 
26             if(r>1) sum+=B[r-2][c];
27             if(c>0) sum+=B[r-1][c-1];
28             if(c<n-1) sum+=B[r-1][c+1];
29             B[r][c]=sum%2;
30             if(A[r][c]==1&&B[r][c]==0) return INF;//违法，不能把1变为0 
31         }
32     }
33     int cnt=0;
34     for(int r=0;r<n;r++)
35     {
36         for(int c=0;c<n;c++)
37         {
38             if(A[r][c]!=B[r][c]) cnt++;
39         }
40     }
41     return cnt;
42 } 
43 int main()
44 {
45     int r,c;//行、列
46     int i,j;
47     int T;
48     int ans=INF;//初始化为最大值 
49     scanf("%d",&T);
50     while(T)
51     {
52         ans=INF;
53         scanf("%d",&n);
54         for(i=0;i<n;i++)
55         {
56             for(j=0;j<n;j++)
57             {
58                 scanf("%d",&A[i][j]);
59             }
60         }
61         for(int s=0;s<(1<<n);s++)//1<<n等于2^n，不用pow，比较方便 
62         {
63             ans=min(ans,check(s));//不断更新最小ans 
64         }
65         if(ans==INF) ans=-1;//没找到答案 
66         printf("%d %d\n",T,ans);
67         T--;
68     } 
69     return 0;
70 }