纯暴力枚举 80 分

#include <bits/stdc++.h>
using namespace std;
int a[10][10];
// “每行每列每个3x3”的“1~9”是否出现过
bool row[10][10], col[10][10], x33[10][10];
// get33(x,y) 获取在哪个小方块
int get33(int x, int y)
{
    int X = (x - 1) / 3 + 1;
    int Y = (y - 1) / 3 + 1;
    return (X - 1) * 3 + Y;
}
// 获取对应的分值
int getScore(int x, int y)
{
    int X = min(x, 9 - x + 1);
    int Y = min(y, 9 - y + 1);
    return min(5 + X, 5 + Y);
}
// 所有 0
vector<pair<int, int>> v;
int score; // 得分
int ans;   // 最大得分
void dfs(int now)
{
    if (now == v.size())
    {
        ans = max(ans, score);
        return;
    }
    int x = v[now].first;
    int y = v[now].second;
    for (int i = 1; i <= 9; i++)
    {
        if (!row[x][i] && !col[y][i] && !x33[get33(x, y)][i])
        {
            row[x][i] = true;
            col[y][i] = true;
            x33[get33(x, y)][i] = true;
            score += getScore(x, y) * i;
            dfs(now + 1);
            row[x][i] = false;
            col[y][i] = false;
            x33[get33(x, y)][i] = false;
            score -= getScore(x, y) * i;
        }
    }
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    for (int i = 1; i <= 9; i++)
        for (int j = 1; j <= 9; j++)
            cin >> a[i][j];
    // 处理基础得分、及“每行每列每个3x3”的“1~9”是否出现过
    for (int i = 1; i <= 9; i++)
        for (int j = 1; j <= 9; j++)
        {
            int now = a[i][j];
            row[i][now] = true;
            col[j][now] = true;
            x33[get33(i, j)][now] = true;
            score += getScore(i, j) * now;
        }
    // 所有为 0 的位置放入数组
    for (int i = 1; i <= 9; i++)
        for (int j = 1; j <= 9; j++)
            if (a[i][j] == 0)
                v.push_back(make_pair(i, j));
    ans = -1;
    dfs(0);
    cout << ans;
    return 0;
}

暴力枚举基础上玄学优化 100 分

#include <bits/stdc++.h>
using namespace std;
int a[10][10];
// “每行每列每个3x3”的“1~9”是否出现过
bool row[10][10], col[10][10], x33[10][10];
// get33(x,y) 获取在哪个小方块
int get33[10][10] = {
    0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
    0, 1, 1, 1, 2, 2, 2, 3, 3, 3,
    0, 1, 1, 1, 2, 2, 2, 3, 3, 3,
    0, 1, 1, 1, 2, 2, 2, 3, 3, 3,
    0, 4, 4, 4, 5, 5, 5, 6, 6, 6,
    0, 4, 4, 4, 5, 5, 5, 6, 6, 6,
    0, 4, 4, 4, 5, 5, 5, 6, 6, 6,
    0, 7, 7, 7, 8, 8, 8, 9, 9, 9,
    0, 7, 7, 7, 8, 8, 8, 9, 9, 9,
    0, 7, 7, 7, 8, 8, 8, 9, 9, 9};
int getScore[10][10] = {
    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};
// 所有 0
vector<pair<int, int>> v;
int score; // 得分
int ans;   // 最大得分
void dfs(int now)
{
    if (now == v.size())
    {
        ans = max(ans, score);
        return;
    }
    if (score + ((int)v.size() - now) * 9 * 10 <= ans)
        return;
    int x = v[now].first;
    int y = v[now].second;
    for (int i = 1; i <= 9; i++)
    {
        if (!row[x][i] && !col[y][i] && !x33[get33[x][y]][i])
        {
            row[x][i] = true;
            col[y][i] = true;
            x33[get33[x][y]][i] = true;
            score += getScore[x][y] * i;
            dfs(now + 1);
            row[x][i] = false;
            col[y][i] = false;
            x33[get33[x][y]][i] = false;
            score -= getScore[x][y] * i;
        }
    }
}
// 每一个方块有几个 0，以此为依据排列所有 0
int cnt0[10];
bool cmp(pair<int, int> x, pair<int, int> y)
{
    return cnt0[get33[x.first][x.second]] <
           cnt0[get33[y.first][y.second]];
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    for (int i = 1; i <= 9; i++)
        for (int j = 1; j <= 9; j++)
            cin >> a[i][j];
    // 处理基础得分、及“每行每列每个3x3”的“1~9”是否出现过
    // 以及每一个小方块 0 的数量
    for (int i = 1; i <= 9; i++)
        for (int j = 1; j <= 9; j++)
        {
            int now = a[i][j];
            row[i][now] = true;
            col[j][now] = true;
            x33[get33[i][j]][now] = true;
            score += getScore[i][j] * now;
            cnt0[get33[i][j]] += (now == 0);
        }
    // 所有为 0 的位置放入数组
    for (int i = 1; i <= 9; i++)
        for (int j = 1; j <= 9; j++)
            if (a[i][j] == 0)
                v.push_back(make_pair(i, j));
    // 所有 0 按照所在行的 0 的数量排序
    stable_sort(v.begin(), v.end(), cmp);
    ans = -1;
    dfs(0);
    cout << ans;
    return 0;
}