uva 11464 Even Parity

https://vjudge.net/problem/UVA-11464

题意：

给出一个0，1矩阵，现在要求把这个矩阵中的某些0改为1，使得这个矩阵中每个格子的上下左右格子（如果存在）的值之和为偶数，问最少的改变次数，不能达到要求输出-1。

思路：

其实，只要第一行的状态定了，接下来所有行的状态就已经定了，这是经过手算得出的结果。根据一个格子的上左右的值之和，就可以确定它下面的格子的状态。

那么，只需要枚举第一行的状态就可以了，用二进制枚举的方法。

接下来，判断这个矩阵是否满足要求，注意的地方是，如果说原矩阵中为1的在改变后的矩阵中为0，那么这个肯定是不符合要求的，因为只能把0改为1，不能把1改为0。

代码：

 1 #include <stdio.h>
 2 #include <string.h>
 3 #include <algorithm>
 4 using namespace std;
 5 
 6 int a[20][20];
 7 int b[20][20];
 8 
 9 int main()
10 {
11     int t;
12 
13     scanf("%d",&t);
14 
15     int cas =0 ;
16 
17     while (t--)
18     {
19         int n;
20 
21         scanf("%d",&n);
22 
23         for (int i = 0;i < n;i++)
24             for (int j = 0;j < n;j++)
25             scanf("%d",&a[i][j]);
26 
27         int k = (1 << n);
28 
29         int ans = 1000000;
30 
31         for (int i = 0;i < k;i++)
32         {
33             for (int j = 0;j < n;j++)
34             {
35                 if ((1 << j) & i) b[0][j] = 1;
36                 else b[0][j] = 0;
37             }
38 
39             for (int x = 0;x < n - 1;x++)
40                 for (int y = 0;y < n;y++)
41             {
42                 int sum = 0;
43 
44                 if (x - 1 >= 0) sum += b[x-1][y];
45                 if (y - 1 >= 0) sum += b[x][y-1];
46                 if (y + 1 < n) sum += b[x][y+1];
47 
48                 if (sum & 1) b[x+1][y] = 1;
49                 else b[x+1][y] = 0;
50             }
51 
52             int tmp = 0;
53 
54             bool f = 0;
55 
56             for (int x = 0;x < n;x++)
57                 for (int y = 0;y < n;y++)
58             {
59 
60                 if (f) break;
61 
62                 if (a[x][y] == 0 && b[x][y] == 1)
63                 {
64                     tmp++;
65                 }
66                 else if (a[x][y] == 1 && b[x][y] == 0)
67                 {
68                     f = 1;
69                     break;
70                 }
71             }
72 
73 
74             if (f) continue;
75             else ans = min(ans,tmp);
76         }
77 
78         if (ans == 1000000)
79         {
80             printf("Case %d: %d
",++cas,-1);
81         }
82         else printf("Case %d: %d
",++cas,ans);
83     }
84 
85     return 0;
86 }