记录编号	464412	评测结果	AAAAAAAAAAAAAAAAAAAA
题目名称	[NOIP 2009]靶形数独	最终得分	100
用户昵称	CSU_Turkey	是否通过	通过
代码语言	C++	运行时间	1.718 s
提交时间	2017-10-25 19:15:20	内存使用	0.32 MiB

#include<bits/stdc++.h>
using namespace std;
int a[10][10],dx[10][10],dy[10][10],dz[30][10],Max=-1;
int get(int x,int y){
	return (x-1)/3*10+(y-1)/3;
}
int Get(int x,int y){
	if(x==5&&y==5)return 10;
	if(x>=4&&x<=6&&y>=4&&y<=6)return 9;
	if(x>=3&&x<=7&&y>=3&&y<=7)return 8;
	if(x>=2&&x<=8&&y>=2&&y<=8)return 7;
	return 6;
}
void dfs(){
	int tem=10,x,y;
	for(int i=1;i<=9;i++){
		for(int j=1;j<=9;j++){
			if(a[i][j])continue;
			int s=0;
			for(int k=1;k<=9;k++){
				if(dx[i][k]|dy[j][k]|dz[get(i,j)][k])continue;
				s++;
			}
			if(s<tem){
				tem=s;
				x=i;
				y=j;
			}
		}
	}
	if(tem==10){
		int ans=0;
		for(int i=1;i<=9;i++){
			for(int j=1;j<=9;j++){
				ans+=Get(i,j)*a[i][j];
			}
		}
		Max=max(Max,ans);
		return ;
	}
	for(int i=1;i<=9;i++){
		if(dx[x][i]|dy[y][i]|dz[get(x,y)][i])continue;
		dx[x][i]=1;dy[y][i]=1;dz[get(x,y)][i]=1;a[x][y]=i;
		dfs();
		dx[x][i]=0;dy[y][i]=0;dz[get(x,y)][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++){
			scanf("%d",&a[i][j]);
			dx[i][a[i][j]]=1;
			dy[j][a[i][j]]=1;
			dz[get(i,j)][a[i][j]]=1;
		}
	}
	dfs();
	printf("%d",Max);
	return 0;
}