UVa11464 Even Parity

原題転送:http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=2459
一般的な考えは各要素を列挙することであり、2255の状況があり、明らかに耐えられない.制約条件はある要素の周囲の上下左右の4つの要素の和が偶数でなければならないことに注意して、この条件を利用して、私達は簡単に2255種類の情況の中で不法な情況を取り除いて合法的な情況を残すことができて、そしてこれらの合法的な情況の中で最も良い問題に合ってデータを入力する情況を選択します.では、第1行を列挙するだけで、第1行から第2行、さらに第3行...第n行を押し出すことができる.直接深さ検索比較,複雑度O(2 n*n 2).


View Code

 1 #include <stdio.h>
 2 #include <string.h>
 3 #define INF 0x3f3f3f3f
 4 #define N 20
 5 int n, g[N][N], p[N][N], a[N], min;
 6 
 7 void make()
 8 {
 9     int v, i, j;
10     for(i = 1; i <= n; i ++)
11         p[1][i] = a[i];
12     for(i = 2; i <= n; i ++)
13     {
14         for(j = 1; j <= n; j ++)
15         {
16             v = p[i - 2][j] + p[i - 1][j - 1] + p[i - 1][j + 1];
17             p[i][j] = ((v & 1) ? 1 : 0);
18         }
19     }
20 }
21 
22 int cal()
23 {
24     int i, j, cnt = 0;
25     for(i = 1; i <= n; i ++)
26     {
27         for(j = 1; j <= n; j ++)
28         {
29             if(g[i][j] == 1 && p[i][j] == 0)
30                 return INF;
31             if(g[i][j] == 0 && p[i][j] == 1)
32                 cnt ++;
33         }
34     }
35     return cnt;
36 }
37 
38 void dfs(int d)
39 {
40     if(d == n+1)
41     {
42         make();
43         int tmp = cal();
44         if(tmp < min)
45             min = tmp;
46         return ;
47     }
48     a[d] = 0;
49     dfs(d + 1);
50     a[d] = 1;
51     dfs(d + 1);
52 }
53 
54 int main()
55 {
56     int t, cas, i, j;
57     scanf("%d", &t);
58     for(cas = 1; cas <= t; cas ++)
59     {
60         scanf("%d", &n);
61         memset(p, 0, sizeof p);
62         for(i = 1; i <= n; i ++)
63             for(j = 1; j <= n; j ++)
64                 scanf("%d", &g[i][j]);
65                 
66         min = INF;
67         dfs(1);
68         if(min == INF)
69             printf("Case %d: %d
", cas, -1);
70         else
71             printf("Case %d: %d
", cas, min);
72     }
73     return 0;
74 }