记录编号	126986	评测结果	AAAAAAAAAAAAAAAAAAAA
题目名称	[NOIP 2009]靶形数独	最终得分	100
用户昵称	席一鸣	是否通过	通过
代码语言	C++	运行时间	2.404 s
提交时间	2014-10-14 19:45:15	内存使用	0.31 MiB

#include<cmath>
#include<cstdio>
#include<iostream>
using namespace std;
int a[10][10],h[10],hs[10],ss[10],nine[10],sort[10],q[10],ans=-1,st=511;
void swap(int*a,int*b)
{
	*a^=*b;
	*b^=*a;
	*a^=*b;
}
int ten(int x)
{
	return(int)log2(x)+1;
}
void dfs(int k)
{
	int c,i,j,l,get,num,pos,p;
	if(k==10)
	{
		c=a[5][5]*10;
		for(l=2;l<=5;l++)
		{
			for(i=l;i<=10-l;i++)
				c+=(4+l)*(a[i][l-1]+a[i][11-l]);
			for(j=l;j<=10-l;j++)
				c+=(4+l)*(a[l-1][j]+a[11-l][j]);
			c+=(4+l)*(a[l-1][l-1]+a[l-1][11-l]+a[11-l][l-1]+a[11-l][11-l]);
		}
		ans=max(ans,c);
	}
	else
	{
		i=sort[k];
		pos=st&~h[i];
		p=pos&-pos;
		h[i]|=p;
		j=ten(p);
		get=st&~(hs[i]|ss[j]|nine[(i-1)/3*3+(j-1)/3+1]);
		while(get)
		{
			num=get&-get;
			get^=num;
			a[i][j]=ten(num);
			hs[i]|=num;
			ss[j]|=num;
			nine[(i-1)/3*3+(j-1)/3+1]|=num;
			if(pos==p)
				dfs(k+1);
			else
				dfs(k);
			hs[i]^=num;
			ss[j]^=num;
			nine[(i-1)/3*3+(j-1)/3+1]^=num;
		}
		h[i]^=p;
	}
}
main()
{
	freopen("sudoku.in","r",stdin);
	freopen("sudoku.out","w",stdout);
	int i,j,k=1;
	for(i=1;i<=9;i++)
		for(j=1;j<=9;j++)
		{
			sort[i]=i;
			cin>>a[i][j];
			if(a[i][j])
			{
				h[i]|=1<<(j-1);
				if(((hs[i]|ss[j]|nine[(i-1)/3*3+(j-1)/3+1])&(1<<(a[i][j]-1)))==1)
				{
					cout<<-1;
					return 0;
				}
				hs[i]|=1<<(a[i][j]-1);
				ss[j]|=1<<(a[i][j]-1);
				nine[(i-1)/3*3+(j-1)/3+1]|=1<<(a[i][j]-1);
			}
			else
				q[i]++;
		}
	for(i=1;i<9;i++)
		for(j=i+1;j<=9;j++)
			if(q[sort[i]]>q[sort[j]])
				swap(&sort[i],&sort[j]);
	while(!q[sort[k]])
		k++;
	dfs(k);
	cout<<ans;
}