比赛 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;
}