比赛 |
20200109 |
评测结果 |
AAAAAAAAAAAAAAAAAAAA |
题目名称 |
靶形数独 |
最终得分 |
100 |
用户昵称 |
云卷云书 |
运行时间 |
2.610 s |
代码语言 |
C++ |
内存使用 |
13.66 MiB |
提交时间 |
2019-12-25 21:51:23 |
显示代码纯文本
#include<bits/stdc++.h>
using namespace std;
int a[10][10],b[100][4],ans=-1,now=0,u;
bool v[4][10][10];
struct node{
int num,r;
};
node s[10];
bool cmp(node x,node y){
return x.num<y.num;
}
const int score[10][10]=
{{0,0,0,0,0,0,0,0,0,0},
{0,6,6,6,6,6,6,6,6,6},
{0,6,7,7,7,7,7,7,7,6},
{0,6,7,8,8,8,8,8,7,6},
{0,6,7,8,9,9,9,8,7,6},
{0,6,7,8,9,10,9,8,7,6},
{0,6,7,8,9,9,9,8,7,6},
{0,6,7,8,8,8,8,8,7,6},
{0,6,7,7,7,7,7,7,7,6},
{0,6,6,6,6,6,6,6,6,6}};
void init(){
for(int i=1;i<=9;i++) s[i].r=i;
for(int i=1;i<=9;i++)
for(int j=1;j<=9;j++){
cin>>a[i][j];
int x=a[i][j];
int g=(i-1)/3*3+(j-1)/3+1;
if(x)
v[0][i][x]=v[1][j][x]=v[2][g][x]=1,now+=x*score[i][j];
else s[i].num++;
}
sort(s+1,s+10,cmp);
for(int i=1;i<=9;i++)
{
for(int j=1;j<=9;j++)
if(a[s[i].r][j]==0)
b[u][0]=s[i].r,b[u][1]=j,b[u++][2]=(s[i].r-1)/3*3+(j-1)/3+1;
}
/*cout<<endl;
for(int i=0;i<u;i++)
cout<<b[i][0]<<' '<<b[i][1]<<' '<<b[i][2]<<endl;*/
}
void dfs(int p,int sum){
if(p==u){
ans=max(ans,sum);
return ;
}
int h=b[p][0],l=b[p][1],g=b[p][2];
for(int i=1;i<=9;i++){
if(!v[0][h][i]&&!v[1][l][i]&&!v[2][g][i]){
v[0][h][i]=v[1][l][i]=v[2][g][i]=1;
dfs(p+1,sum+i*score[h][l]);
v[0][h][i]=v[1][l][i]=v[2][g][i]=0;
}
}
return ;
}
int main(){
freopen("sudoku.in","r",stdin);
freopen("sudoku.out","w",stdout);
init();
dfs(0,now);
cout<<ans;
}