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