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
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
| #include <algorithm>
#include <iostream>
#include <cstring>
#include <cstdio>
#include <vector>
#define FILE_IN(__fname) freopen(__fname, "r", stdin)
#define FILE_OUT(__fname) freopen(__fname, "w", stdout)
#define rap(a,s,t,i) for (int a = s; a <= t; a += i)
#define basketball(a,t,s,i) for (int a = t; a > s; a -= i)
#define countdown(s) while (s --> 0)
#define IMPROVE_IO() std::ios::sync_with_stdio(false)
using std::cin;
using std::cout;
using std::endl;
typedef long long int lli;
int getint() { int x; scanf("%d", &x); return x; }
lli getll() { long long int x; scanf("%lld", &x); return x; }
const int MAXN = 9 + 2;
const int weight[11][11] = {
{0, 0, 0, 0, 0, 0, 0, 0, 0, 0},
{0, 6, 6, 6, 6, 6, 6, 6, 6, 6},
{0, 6, 7, 7, 7, 7, 7, 7, 7, 6},
{0, 6, 7, 8, 8, 8, 8, 8, 7, 6},
{0, 6, 7, 8, 9, 9, 9, 8, 7, 6},
{0, 6, 7, 8, 9,10, 9, 8, 7, 6},
{0, 6, 7, 8, 9, 9, 9, 8, 7, 6},
{0, 6, 7, 8, 8, 8, 8, 8, 7, 6},
{0, 6, 7, 7, 7, 7, 7, 7, 7, 6},
{0, 6, 6, 6, 6, 6, 6, 6, 6, 6},
};
const int area[11][11] = {
{0, 0, 0, 0, 0, 0, 0, 0, 0, 0},
{0, 1, 1, 1, 6, 6, 6, 9, 9, 9},
{0, 1, 1, 1, 6, 6, 6, 9, 9, 9},
{0, 1, 1, 1, 6, 6, 6, 9, 9, 9},
{0, 8, 8, 8, 7, 7, 7, 3, 3, 3},
{0, 8, 8, 8, 7, 7, 7, 3, 3, 3},
{0, 8, 8, 8, 7, 7, 7, 3, 3, 3},
{0, 4, 4, 4, 5, 5, 5, 2, 2, 2},
{0, 4, 4, 4, 5, 5, 5, 2, 2, 2},
{0, 4, 4, 4, 5, 5, 5, 2, 2, 2},
};
struct Order {
int id, siz;
Order(int _id = 0, int _siz = 0) : id(_id), siz(_siz) {}
bool operator < (const Order &that) const {
return siz > that.siz;
}
} order[MAXN];
int n = 9, sd[MAXN][MAXN], linesiz[MAXN], rowsiz[MAXN];
bool lineUsed[MAXN][10], rowUsed[MAXN][10], areaUsed[MAXN][10];
int ans = 0, vis = 0;
void print() {
puts("");
for (int i = 1; i <= n; ++i) {
for (int j = 1; j <= n; ++j) {
printf("%d%c", sd[i][j], j == n ? '\n' : ' ');
}
}
puts("");
}
void placeNum(int x, int y, int num) {
sd[x][y] = num;
++linesiz[x]; ++rowsiz[y];
lineUsed[x][num] = rowUsed[y][num] = true;
areaUsed[area[x][y]][num] = true;
}
void displaceNum(int x, int y, int num) {
sd[x][y] = 0;
--linesiz[x]; --rowsiz[y];
lineUsed[x][num] = rowUsed[y][num] = false;
areaUsed[area[x][y]][num] = false;
}
void DFS(int line = 0, int row = 0, int totalPlaced = 0) {
if (totalPlaced == 81) {
vis = 1;
int fans = 0;
for (int i = 1; i <= n; ++i) {
for (int j = 1; j <= n; ++j) {
fans += sd[i][j] * weight[i][j];
}
}
ans = std::max(ans, fans);
return;
}
for (int num = 1; num <= 9; ++num) {
if (lineUsed[line][num]
|| rowUsed[row][num]
|| areaUsed[area[line][row]][num]) continue;
placeNum(line, row, num);
int nextLine = 0, maxSize = -1;
for (int i = 1; i <= n; ++i) {
if (maxSize < linesiz[i] && linesiz[i] != 9) {
maxSize = linesiz[i]; nextLine = i;
}
}
int nextRow = 0; maxSize = -1;
for (int i = 1; i <= n; ++i) {
if (maxSize < rowsiz[i] && !sd[nextLine][i]) {
maxSize = rowsiz[i]; nextRow = i;
}
}
DFS(nextLine, nextRow, totalPlaced + 1);
displaceNum(line, row, num);
}
}
int main() {
int maxSiz1 = -1, lc = 0, maxSiz2 = -1, rc = 0, cnt = 0;
for (int i = 1; i <= n; ++i) {
for (int j = 1; j <= n; ++j) {
sd[i][j] = getint();
if (sd[i][j] == 0) continue;
cnt += (sd[i][j] > 0);
linesiz[i] += (sd[i][j] > 0);
rowsiz[j] += (sd[i][j] > 0);
lineUsed[i][sd[i][j]]
= rowUsed[j][sd[i][j]] = true;
areaUsed[area[i][j]][sd[i][j]] = true;
}
if (maxSiz1 < linesiz[i] && linesiz[i] != 9) {
lc = i; maxSiz1 = linesiz[i];
}
}
for (int i = 1; i <= n; ++i) {
if (maxSiz2 < rowsiz[i] && !sd[lc][i]) {
rc = i; maxSiz2 = rowsiz[i];
}
}
DFS(lc, rc, cnt);
if (!vis) puts("-1");
else printf("%d\n", ans);
return 0;
}
|
