比赛 |
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;
}