记录编号	604572	评测结果	AAAAAAAAAAAAAAAAAAAA
题目名称	407.[NOIP 2009]靶形数独	最终得分	100
用户昵称	ChenBp	是否通过	通过
代码语言	C++	运行时间	1.848 s
提交时间	2025-08-10 16:48:29	内存使用	3.68 MiB

#include <algorithm>
#include <cmath>
#include <cstdio>
#include <iostream>
#define ll long long
using namespace std;
inline int read() {
    int x = 0, f = 1;
    char ch = getchar();
    while (ch < '0' || ch > '9') {
        if (ch == '-')
            f = -1;
        ch = getchar();
    }
    while (ch >= '0' && ch <= '9')
        x = x * 10 + ch - '0', ch = getchar();
    return x * f;
}
void write(int x) {
    if (x < 0)
        putchar('-'), x = -x;
    if (x > 9)
        write(x / 10);
    putchar(x % 10 + '0');
    return;
}
constexpr int f[9][9] = {
    {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 g[9][9];
int h[9], l[9], gr[3][3];
int num = 0;
struct node {
    short x, y;
} s[100];
int lowbit(int x) {
    return x & (-x);
}
ll ans = -1;
void dfs(ll t) {
    ll now = 0;
    for (int i = 0; i < 9; i++)
        for (int j = 0; j < 9; j++)
            now += f[i][j] * g[i][j];

    ll remain = 0;
    for (ll i = t; i <= num; i++) {
        int x = s[i].x, y = s[i].y;
        remain += f[x][y] * 9;
    }
    if (now + remain <= ans)
        return;

    if (t == num + 1) {
        ans = max(ans, now);
        return;
    }
    int min_cnt = 10, sel = -1, sel_w = 0;
    for (ll i = t; i <= num; i++) {
        int x = s[i].x, y = s[i].y;
        int w = 0, cnt = 0;
        for (int k = 1; k <= 9; k++) {
            if ((((h[x] >> k) & 1) + ((l[y] >> k) & 1) + ((gr[x / 3][y / 3] >> k) & 1)) == 0) {
                w |= 1 << k;
                cnt++;
            }
        }
        if (cnt == 0)
            return;
        if (cnt < min_cnt) {
            min_cnt = cnt;
            sel = i;
            sel_w = w;
            if (cnt == 1)
                break;
        }
    }

    swap(s[t], s[sel]);
    int x = s[t].x, y = s[t].y;
    int w = sel_w;

    while (w) {
        int k = log2(lowbit(w));
        h[x] |= 1 << k;
        l[y] |= 1 << k;
        gr[x / 3][y / 3] |= 1 << k;
        g[x][y] = k;

        dfs(t + 1);

        g[x][y] = 0;
        h[x] &= (~(1 << k));
        l[y] &= (~(1 << k));
        gr[x / 3][y / 3] &= (~(1 << k));
        w -= lowbit(w);
    }
    swap(s[t], s[sel]);
}
int main() {
    for (int i = 0; i < 9; i++) {
        for (int j = 0; j < 9; j++) {
            g[i][j] = read();
            if (g[i][j] == 0)
                continue;
            h[i] |= 1 << g[i][j];
            l[j] |= 1 << g[i][j];
            gr[i / 3][j / 3] |= 1 << g[i][j];
        }
    }

    //    for(int i=0;i<9;i++){while(h[i]){cout<<log2(bitset(h[i]))<<"
    //    ";h[i]-=bitset(h[i]);}cout<<endl;} for(int
    //    i=0;i<9;i++){while(l[i]){cout<<log2(bitset(l[i]))<<" ";l[i]-=bitset(l[i]);}cout<<endl;}
    //    for(int i=0;i<3;i++){for(int j=0;j<3;j++){while(gr[i][j]){cout<<log2(bitset(gr[i][j]))<<"
    //    ";gr[i][j]-=bitset(gr[i][j]);}cout<<endl;}}

    for (int i = 0; i < 9; i++) {
        for (int j = 0; j < 9; j++) {
            if (g[i][j] != 0)
                continue;
            num++;
            s[num].x = i;
            s[num].y = j;
        }
    }
    // sort(s + 1, s + 1 + num, cmp);
    //    for(int i=1;i<=num;i++){cout<<s[i].x<<" "<<s[i].y<<" "<<s[i].sum<<"\n";
    dfs(1);
    write(ans);
    return 0;
}