rt

#include <bits/stdc++.h>
using namespace std;
typedef pair<int, pair<int, int>> PIII;
const int N = 9;
bool row[N][N + 1], col[N][N + 1], block[3][3][N + 1];
int g[N][N], ans = 0;
int color[N][N] = {
        {6, 6, 6, 6, 6, 6, 6, 6, 6},
        {6, 7, 7, 7, 7, 7, 7, 7, 6},
        {6, 7, 8, 8, 8, 8, 8, 7, 6},
        {6, 7, 8, 9, 9, 9, 8, 7, 6},
        {6, 7, 8, 9, 10, 9, 8, 7, 6},
        {6, 7, 8, 9, 9, 9, 8, 7, 6},
        {6, 7, 8, 8, 8, 8, 8, 7, 6},
        {6, 7, 7, 7, 7, 7, 7, 7, 6},
        {6, 6, 6, 6, 6, 6, 6, 6, 6}
    };
priority_queue<PIII, vector<PIII>, greater<PIII>> q;
vector<PIII> order;
void init(){
    for(int i = 0; i < N; i ++ )
        for(int j = 0; j < N; j ++ ){
            if(g[i][j]) continue;
            int res = 0;
            for(int k = 1; k <= 9; k ++ ){
                if(!row[i][k]) res ++ ;
                if(!col[j][k]) res ++ ;
                if(!block[i / 3][j / 3][k]) res ++ ;
            }
            q.push({res, {i, j}});
        }
    while(!q.empty()){
        order.push_back(q.top());
        q.pop();
    }
    order.push_back({1e9, {-1, -1}});
    reverse(order.begin(), order.end());
}
void dfs(int r, int c, int sum){
    if(r == -1 && c == -1){
        ans = max(ans, sum);
        return;
    }
    for(int i = 1; i <= 9; i ++ ){
        if(row[r][i] || col[c][i] || block[r / 3][c / 3][i]) continue;
        row[r][i] = col[c][i] = block[r / 3][c / 3][i] = true;
        g[r][c] = i;
        auto t = order.back();
        order.pop_back();
        dfs(t.second.first, t.second.second, sum + i * color[r][c]);
        row[r][i] = col[c][i] = block[r / 3][c / 3][i] = false;
        order.push_back(t);
    }
}
int main(){
    int sum = 0;
    for(int i = 0; i < N; i ++ )
        for(int j = 0; j < N; j ++ ){
            scanf("%d", &g[i][j]);
            if(g[i][j]) row[i][g[i][j]] = col[j][g[i][j]] = block[i / 3][j / 3][g[i][j]] = true;
            sum += g[i][j] * color[i][j];
        }
    init();
    auto t = order.back();
    order.pop_back();
    dfs(t.second.first, t.second.second, sum);
    if(!ans) puts("-1");
    else printf("%d", ans);
    return 0;
}

实测手搓队列慢0.05s， 拼尽全力无法优化