比赛 20250409练习赛 评测结果 AAAAAAAATAAAAAAATTTT
题目名称 靶形数独 最终得分 75
用户昵称 ChenBp 运行时间 12.106 s
代码语言 C++ 内存使用 3.39 MiB
提交时间 2025-04-09 21:31:50
显示代码纯文本
#pragma GCC optimize(2)
#include <iostream>
#include <cstdio>
#include <cmath>
#include <algorithm>
#define ll long long 
using namespace std;
const 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}
};
short g[9][9];
short h[9],l[9],gr[3][3];
int num=0;
struct node{
    short x,y,sum=0,w;
}s[100];
bool cmp(node x,node y){
    return x.sum<y.sum;
}
int bitset(int x){
    return x&(-x);
}
ll ans=-1;
void dfs(ll t){
    if(t==num+1){
        ll now=0;
        for(int i=0;i<9;i++){
            for(int j=0;j<9;j++){
                now+=f[i][j]*g[i][j];
            }
        }
        ans=max(ans,now);
        return;
    }
    int w=s[t].w;
    int x=s[t].x,y=s[t].y;
    while(w){
        int k=log2(bitset(w));
        if((((h[x]>>k)&1)+((l[y]>>k)&1)+((gr[x/3][y/3]>>k)&1))==0){
            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-=bitset(w);
    }
}
int main(){
    freopen("sudoku.in","r",stdin);
    freopen("sudoku.out","w",stdout);
    for(int i=0;i<9;i++){
        for(int j=0;j<9;j++){
            cin>>g[i][j];
            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;
            for(int k=1;k<=9;k++){
                if((((h[i]>>k)&1)+((l[j]>>k)&1)+((gr[i/3][j/3]>>k)&1))==0){
                    s[num].sum++;
                    s[num].w|=1<<k;
                }
            }
        }
    }
    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);
    cout<<ans;
    return 0;
}