给你一个n*n的矩阵，你的任务是把尽量少的0变成1，使得每个数字的上下左右元素之和是偶数。
直接暴力肯定会超时，找到行与行之间的关系，可以发现只要枚举第一行的所有情况，后面行都可以算出来。
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74 |
#include <cstdio>#include <cstring>#include <algorithm>using
namespace
std;const
int
maxn = 16;const
int
INF = 2100000000 / 2;int
mat[maxn][maxn],ans,n;int
getsum(int
x,int
y,int
m[maxn][maxn]) { int
ans = 0; if(x > 1) ans += m[x - 1][y]; if(x < n) ans += m[x + 1][y]; if(y > 1) ans += m[x][y - 1]; if(y < n) ans += m[x][y + 1]; return
ans;}int
check() { int
matA[maxn][maxn],ret = 0; for(int
i = 1;i <= n;i++) { for(int
j = 1;j <= n;j++) { matA[i][j] = mat[i][j]; } } for(int
i = 1;i <= n;i++) { for(int
j = 1;j <= n;j++) { if(getsum(i,j,matA) & 1) { if(i == n || matA[i + 1][j] == 1) { return
INF; } else
{ matA[i + 1][j] = 1; ret++; } } } } return
ret;}void
dfs(int
pos,int
ch) { if(pos > n) return; ans = min(check() + ch,ans); dfs(pos + 1,ch); if(mat[1][pos] == 0) { mat[1][pos] = 1; ans = min(ans,check() + ch + 1); dfs(pos + 1,ch + 1); mat[1][pos] = 0; }}int
main() { int
T; scanf("%d",&T); for(int
kase = 1;kase <= T;kase++) { scanf("%d",&n); for(int
i = 1;i <= n;i++) { for(int
j = 1;j <= n;j++) { scanf("%d",&mat[i][j]); } } ans = INF; dfs(1,0); printf("Case %d: ",kase); if(ans == INF) { puts("-1"); } else
{ printf("%d\n",ans); } } return
0;} |
原文：http://www.cnblogs.com/rolight/p/3541377.html