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
| #include <bits/stdc++.h>
using namespace std;
const int maxn = 9;
int ans = -1, a[maxn][maxn];
int row[maxn], col[maxn], grid[maxn], cnt[1 << maxn];
int lowbit(int x) { return x & -x; }
int g(int x, int y) { return (x / 3) * 3 + (y / 3); }
int p(int x, int y) { return min(min(x, 8 - x), min(y, 8 - y)) + 6; }
void flip(int x, int y, int v) {
row[x] ^= 1 << v, col[y] ^= 1 << v, grid[g(x, y)] ^= 1 << v;
}
void dfs(int num, int sum) {
if (!num) {
ans = max(ans, sum);
return;
}
int t = 10, x, y, s;
for (int i = 0; i < maxn; ++i) {
for (int j = 0; j < maxn; ++j) {
if (!a[i][j]) {
s = row[i] & col[j] & grid[g(i, j)];
if (!s) return;
if (cnt[s] < t) {
t = cnt[s], x = i, y = j;
}
}
}
}
s = row[x] & col[y] & grid[g(x, y)];
while (s) {
int v = cnt[lowbit(s) - 1];
a[x][y] = v + 1;
flip(x, y, v);
dfs(num - 1, sum + p(x, y) * (v + 1));
flip(x, y, v);
a[x][y] = 0;
s -= lowbit(s);
}
}
int main() {
cnt[0] = 0;
for (int i = 1; i < (1 << maxn); ++i) cnt[i] = cnt[i & (i - 1)] + 1;
int tot = 0, sum = 0;
for (int i = 0; i < maxn; ++i) row[i] = col[i] = grid[i] = (1 << maxn) - 1;
for (int i = 0; i < maxn; ++i) {
for (int j = 0; j < maxn; ++j) {
cin >> a[i][j];
if (a[i][j]) {
sum += p(i, j) * a[i][j];
flip(i, j, a[i][j] - 1);
} else {
++tot;
}
}
}
dfs(tot, sum);
cout << ans;
return 0;
}
|