记录编号	434873	评测结果	AAAAAAAAAAAAAAAAAAAA
题目名称	[NOIP 2009]靶形数独	最终得分	100
用户昵称	Anonymity	是否通过	通过
代码语言	C++	运行时间	3.594 s
提交时间	2017-08-08 20:40:39	内存使用	0.31 MiB

#include<cstdio>
#include<iostream>
#include<cstring>
#define maxn 11
#define mem(a,b) memset(a,b,sizeof(a))
using namespace std;
inline int read()
{   char c=getchar();int x=0,y=1;
	while(c<'0'||c>'9'){if(c=='-') y=-1;c=getchar();}
	while(c>='0'&&c<='9') x=x*10+c-'0',c=getchar();
	return x*y;
}
int fans,ans,w[maxn][maxn],A[maxn][maxn];
bool ok[maxn][maxn],ok2[maxn][maxn],ok3[5][5][11];
inline bool check(int x,int y,int z)
{	if(ok[x][z]) return 0;
	if(ok2[y][z]) return 0;
	int t1=(x-1)/3+1,t2=(y-1)/3+1;
	if(ok3[t1][t2][z]) return 0;
	return 1;
}
inline int ab(int x){return (x-5>0)?x-5:5-x;}
void dfs()
{
	int smax=10,x=0,y=0;
	for(int i=1;i<=9;i++)
		for(int j=1;j<=9;j++)
			if(!A[i][j])
			{	int tmp=0;
				for(int k=1;k<=9;k++)
					if(check(i,j,k))
						++tmp;
				if(tmp<smax) smax=tmp,x=i,y=j;
			}
	if(smax==10)
	{	ans=0;
		for(int i=1;i<=9;i++)
			for(int j=1;j<=9;j++)
				ans+=w[i][j]*A[i][j];
		fans=max(ans,fans);
	}
	for(int i=1;i<=9;i++)
		if(x&&y&&check(x,y,i))
		{	int t1=(x-1)/3+1,t2=(y-1)/3+1,tmp=0;
			ok[x][i]=1;ok2[y][i]=1;ok3[t1][t2][i]=1;A[x][y]=i;
			dfs();
			ok[x][i]=0;ok2[y][i]=0;ok3[t1][t2][i]=0;A[x][y]=0;
		}
}
int main()
{   freopen("sudoku.in","r",stdin);
	freopen("sudoku.out","w",stdout);
	for(int i=1;i<=9;i++)
		for(int j=1;j<=9;j++)
		{	A[i][j]=read();
			if(A[i][j])
			{	ok[i][A[i][j]]=1;ok2[j][A[i][j]]=1;
				int t1=(i-1)/3+1,t2=(j-1)/3+1;
				ok3[t1][t2][A[i][j]]=1;
			}
		}
	for(int i=1;i<=9;i++)
		for(int j=1;j<=9;j++)
		{	int t1=ab(i),t2=ab(j);
			if(t1==4) w[i][j]=6;
			if(t1==3){if(t2==4) w[i][j]=6;else w[i][j]=7;}
			if(t1==2){if(t2==4) w[i][j]=6;else if(t2==3) w[i][j]=7;else w[i][j]=8;}
			if(t1==1){if(t2==4) w[i][j]=6;else if(t2==3) w[i][j]=7;else if(t2==2) w[i][j]=8;else w[i][j]=9;}
			if(t1==0){if(t2==4) w[i][j]=6;else if(t2==3) w[i][j]=7;else if(t2==2) w[i][j]=8;else if(t2==1) w[i][j]=9;else w[i][j]=10;}
		}
	dfs();
	if(!fans) printf("-1");
	else printf("%d",fans);
	return 0;
}