记录编号	435626	评测结果	AAAAAAAAAAAAAAAAAAAA
题目名称	[NOIP 2009]靶形数独	最终得分	100
用户昵称	BaDBoY	是否通过	通过
代码语言	C++	运行时间	2.625 s
提交时间	2017-08-09 21:37:03	内存使用	0.32 MiB

#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
int a[10][10],score[10][10],ans,tot,ji[100],belong[10][10];
bool hang[10][10],lie[10][10],blo[10][10];
bool check() {
	for(int i=1; i<=9; i++) 
		for(int j=1; j<=9; j++) 
			if(!hang[i][j]||!lie[i][j])return false;
	return true;
}
inline void dfs(int i,int j,int sum) {
	if(i==1&&j==1) {
		if(a[i][j]) {ans=max(ans,sum);return ;}
		int num;
		for(num=1; num<=9; num++) {
			if((hang[1][num]&&!lie[1][num])||(!hang[1][num]&&lie[1][num])) return ;
			if(!hang[1][num]&&!lie[1][num]) break;
		}ans=max(ans,sum+score[1][1]*num);
		return ;
	}
	if(a[i][j]) {
		if(i&1) 
			if(j>1) dfs(i,j-1,sum);
			else dfs(i-1,j,sum);
		else 
			if(j<9)dfs(i,j+1,sum);
			else dfs(i-1,j,sum);
		return ;
	}
	for(int num=1; num<=9; num++) {
		if(hang[i][num]||lie[j][num]||blo[belong[i][j]][num]) continue;
		hang[i][num]=1;  lie[j][num]=1;
		a[i][j]=num;blo[belong[i][j]][num]=1;
		sum+=score[i][j]*num;
		if(i&1) 
			if(j>1) dfs(i,j-1,sum);
		    else dfs(i-1,j,sum);
	    else 
			if(j<9) dfs(i,j+1,sum);
		    else dfs(i-1,j,sum);
		hang[i][num]=0;  lie[j][num]=0;
		a[i][j]=0;   blo[belong[i][j]][num]=0;sum-=score[i][j]*num;
	}
	return ;
}
void init() {
	for(int i=1; i<=3; i++) {
		for(int j=1; j<=3; j++) belong[i][j]=1;
		for(int j=4; j<=6; j++) belong[i][j]=2;
		for(int j=7; j<=9; j++) belong[i][j]=3;
	}
	for(int i=4; i<=6; i++) {
		for(int j=1; j<=3; j++) belong[i][j]=4;
		for(int j=4; j<=6; j++) belong[i][j]=5;
		for(int j=7; j<=9; j++) belong[i][j]=6;
	}
	for(int i=7; i<=9; i++) {
		for(int j=1; j<=3; j++) belong[i][j]=7;
		for(int j=4; j<=6; j++) belong[i][j]=8;
		for(int j=7; j<=9; j++) belong[i][j]=9;
	}
	score[5][5]=10;score[4][4]=score[6][6]=score[4][6]=score[6][4]=score[4][5]=score[5][4]=score[5][6]=score[6][5]=9;
	for(int j=3; j<=7; j++) score[3][j]=score[7][j]=8;
	for(int i=4; i<=6; i++) score[i][3]=score[i][7]=8;
	for(int j=2; j<=8; j++)score[2][j]=score[8][j]=7;
	for(int i=3; i<=7; i++) score[i][2]=score[i][8]=7;
	for(int j=1; j<=9; j++) score[1][j]=score[9][j]=6;
	for(int i=2; i<=8; i++) score[i][1]=score[i][9]=6;
}
int main() {
	freopen("sudoku.in","r",stdin);
	freopen("sudoku.out","w",stdout);
	init();
	int res=0;
	for(int i=1; i<=9; i++) {
		for(int j=1; j<=9; j++) {
			scanf("%d",&a[i][j]);
			if(!a[i][j]) 
				continue;
			res+=a[i][j]*score[i][j];
			hang[i][a[i][j]]=1;
			lie[j][a[i][j]]=1;
			blo[belong[i][j]][a[i][j]]=1;
		}
	}dfs(9,9,res);
	if(!ans) cout<<"-1";
	else cout<<ans;
	return 0;
}