Deep Seek还是太强了

#include <iostream>
#include <cstdio>
#include <algorithm>
using namespace std;

const int N = 9;
int grid[N][N];
int score[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}
};

// 位运算优化：每行、每列、每个九宫格的已用数字
int row[N], col[N], cell[3][3];
int ones[1 << N];  // 快速获取1的个数
int log2[1 << N];  // 快速获取最低位的1的位置
int ans = -1;      // 最大分数
int empty_cnt = 0; // 空格数量

// 预计算ones和log2数组
inline void init() {
    for (int i = 0; i < N; i++) log2[1 << i] = i;
    for (int i = 0; i < 1 << N; i++) {
        int s = 0;
        for (int j = i; j; j -= j & -j) s++;
        ones[i] = s;
    }
}

// 获取(i,j)位置可以填的数字集合
inline int get(int i, int j) {
    return row[i] & col[j] & cell[i / 3][j / 3];
}

// 获取最低位的1的位置（从0开始）
inline int lowbit(int x) {
    return x & -x;
}

// 计算剩余空格的最大可能分数
inline int max_possible_score(int cur_score) {
    return cur_score + empty_cnt * 10 * 9; // 乐观估计：每个空格都得90分（9*10）
}

// DFS搜索，使用最优性剪枝
void dfs(int cur_score, int empty_cnt) {
    // 剪枝：当前分数 + 剩余最大可能分数 <= 当前最优解
    if (cur_score + empty_cnt * 90 <= ans) return;
    
    if (empty_cnt == 0) {
        ans = max(ans, cur_score);
        return;
    }
    
    // 选择可填数字最少的位置（MRV启发式）
    int min_choices = 10;
    int x = -1, y = -1;
    
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++) {
            if (grid[i][j] == 0) {
                int choices = get(i, j);
                int cnt = ones[choices];
                if (cnt < min_choices) {
                    min_choices = cnt;
                    x = i, y = j;
                }
                if (min_choices == 1) break; // 已经是最优选择
            }
        }
        if (min_choices == 1) break;
    }
    
    if (x == -1) return; // 无解
    
    // 获取可填数字，并从大到小尝试
    int available = get(x, y);
    
    // 从大到小尝试数字（优先尝试大数字）
    while (available) {
        // 获取最高位的1（最大的数字）
        int mask = available;
        int digit = 0;
        while (mask) {
            digit = log2[lowbit(mask)];
            mask -= lowbit(mask);
        }
        
        // 清除这个数字
        int t = 1 << digit;
        available ^= t;
        
        // 实际数字是digit+1
        int num = digit + 1;
        
        // 更新状态
        grid[x][y] = num;
        row[x] ^= t;
        col[y] ^= t;
        cell[x / 3][y / 3] ^= t;
        
        dfs(cur_score + num * score[x][y], empty_cnt - 1);
        
        // 恢复状态
        grid[x][y] = 0;
        row[x] ^= t;
        col[y] ^= t;
        cell[x / 3][y / 3] ^= t;
    }
}

int main() {
    init();
    
    // 初始化：所有位置都可以填1-9
    for (int i = 0; i < N; i++) {
        row[i] = col[i] = (1 << N) - 1;
    }
    for (int i = 0; i < 3; i++) {
        for (int j = 0; j < 3; j++) {
            cell[i][j] = (1 << N) - 1;
        }
    }
    
    int cur_score = 0;
    
    // 读入数据并初始化
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++) {
            scanf("%d", &grid[i][j]);
            if (grid[i][j] != 0) {
                int num = grid[i][j];
                int t = 1 << (num - 1);
                
                // 检查冲突
                if (!(row[i] & t) || !(col[j] & t) || !(cell[i / 3][j / 3] & t)) {
                    printf("-1\n");
                    return 0;
                }
                
                row[i] ^= t;
                col[j] ^= t;
                cell[i / 3][j / 3] ^= t;
                cur_score += num * score[i][j];
            } else {
                empty_cnt++;
            }
        }
    }
    
    dfs(cur_score, empty_cnt);
    
    printf("%d\n", ans);
    return 0;
}