比赛 |
20250409练习赛 |
评测结果 |
AAAAAAAAATATAATTAAAA |
题目名称 |
靶形数独 |
最终得分 |
80 |
用户昵称 |
LikableP |
运行时间 |
11.064 s |
代码语言 |
C++ |
内存使用 |
1.52 MiB |
提交时间 |
2025-04-09 20:09:10 |
显示代码纯文本
#pragma GCC optimize(2)
#include <cstdio>
#include <algorithm>
using namespace std;
struct EMPTY {
int x, y;
int avilable;
} empty[81];
bool cmp(EMPTY x, EMPTY y) {
return x.avilable < y.avilable;
}
int w[10][10] = {
{},
{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}
};
int m;
int a[10][10];
bool visx[10][10], visy[10][10], visc[5][5][10];
long long ans = -1;
void calc() {
long long t = 0;
for (int i = 1; i <= 9; ++i) {
for (int j = 1; j <= 9; ++j) {
t += w[i][j] * a[i][j];
}
}
ans = max(ans, t);
// printf("=========\n");
// for (int i = 1; i <= 9; ++i) {
// for (int j = 1; j <= 9; ++j) {
// printf("%d%c", a[i][j], " \n"[j == 9]);
// }
// }
// printf("ANS=%d\n", t);
}
void dfs(int pos) {
if (pos == m + 1) {
calc();
return ;
}
int x = empty[pos].x, y = empty[pos].y;
for (int i = 1; i <= 9; ++i) {
if (visx[x][i]) continue;
if (visy[y][i]) continue;
if (visc[(x - 1) / 3 + 1][(y - 1) / 3 + 1][i]) continue;
visx[x][i] = visy[y][i] = visc[(x - 1) / 3 + 1][(y - 1) / 3 + 1][i] = 1;
a[x][y] = i;
dfs(pos + 1);
visx[x][i] = visy[y][i] = visc[(x - 1) / 3 + 1][(y - 1) / 3 + 1][i] = 0;
}
}
int main() {
freopen("sudoku.in", "r", stdin);
freopen("sudoku.out", "w", stdout);
for (int i = 1; i <= 9; ++i) {
for (int j = 1; j <= 9; ++j) {
scanf("%d", &a[i][j]);
visx[i][a[i][j]] = 1;
visy[j][a[i][j]] = 1;
visc[(i - 1) / 3 + 1][(j - 1) / 3 + 1][a[i][j]] = 1;
if (a[i][j] == 0) {
empty[++m].x = i;
empty[m].y = j;
for (int k = 1; k <= 9; ++k) {
if (visx[i][k] || visy[j][k] || visc[(i - 1) / 3 + 1][(j - 1) / 3 + 1][k]) continue;
empty[m].avilable++;
}
}
}
}
dfs(1);
printf("%lld", ans);
return 0;
}