记录编号	459354	评测结果	AAAAAAAAAAAAAAAAAAAA
题目名称	407.[NOIP 2009]靶形数独	最终得分	100
用户昵称	zeppoe	是否通过	通过
代码语言	C++	运行时间	3.701 s
提交时间	2017-10-12 21:57:53	内存使用	0.29 MiB

#include<cstdio>
#include<cstring>
using namespace std;
int n,ans,rank[6],map[10][10];
bool r[10][10],l[10][10],p[10][10];
//手动笑哭，数组是从第零位开始存的，noip很玄啊。。。 
int g[10][10]={
	0,0,0,0,0,0,0,0,0,0,
	0,1,1,1,2,2,2,3,3,3,
	0,1,1,1,2,2,2,3,3,3,
	0,1,1,1,2,2,2,3,3,3,
	0,4,4,4,5,5,5,6,6,6,
	0,4,4,4,5,5,5,6,6,6,
    0,4,4,4,5,5,5,6,6,6,
	0,7,7,7,8,8,8,9,9,9,
	0,7,7,7,8,8,8,9,9,9,
	0,7,7,7,8,8,8,9,9,9
};

int ra[10][10]={
	0,0,0,0,0,0,0,0,0,0,
	0,1,1,1,1,1,1,1,1,1,
	0,1,2,2,2,2,2,2,2,1,
	0,1,2,3,3,3,3,3,2,1,
	0,1,2,3,4,4,4,3,2,1,
	0,1,2,3,4,5,4,3,2,1,
	0,1,2,3,4,4,4,3,2,1,
	0,1,2,3,3,3,3,3,2,1,
	0,1,2,2,2,2,2,2,2,1,
	0,1,1,1,1,1,1,1,1,1
};

int val;

int mod[100],div[100];

void dfs(int k){
	if(k>81) return void(val>ans?ans=val:0);
	//if(x) 即x不为0，0 false 1 true 手动笑哭 
	int x,y;
	if (mod[k]) x=mod[k],y=div[k]+1;else x=9,y=div[k];
	//从左上角开始搜，先行后列
	if(map[x][y]) return dfs(k+1);
	bool *R=r[x],*L=l[y],*P=p[g[x][y]];
	int i,RA=ra[x][y];
	i=1;
	if((!R[i])&&(!L[i])&&(!P[i])){
		R[i]=L[i]=P[i]=1;
		val+=RA*i;
		dfs(k+1);
		R[i]=L[i]=P[i]=0;
		val-=RA*i;
	}
	i=2;
	if((!R[i])&&(!L[i])&&(!P[i])){
		R[i]=L[i]=P[i]=1;
		val+=RA*i;
		dfs(k+1);
		R[i]=L[i]=P[i]=0;
		val-=RA*i;
	}
	i=3;
	if((!R[i])&&(!L[i])&&(!P[i])){
		R[i]=L[i]=P[i]=1;
		val+=RA*i;
		dfs(k+1);
		R[i]=L[i]=P[i]=0;
		val-=RA*i;
	}
	i=4;
	if((!R[i])&&(!L[i])&&(!P[i])){
		R[i]=L[i]=P[i]=1;
		val+=RA*i;
		dfs(k+1);
		R[i]=L[i]=P[i]=0;
		val-=RA*i;
	}
	i=5;
	if((!R[i])&&(!L[i])&&(!P[i])){
		R[i]=L[i]=P[i]=1;
		val+=RA*i;
		dfs(k+1);
		R[i]=L[i]=P[i]=0;
		val-=RA*i;
	}
	i=6;
	if((!R[i])&&(!L[i])&&(!P[i])){
		R[i]=L[i]=P[i]=1;
		val+=RA*i;
		dfs(k+1);
		R[i]=L[i]=P[i]=0;
		val-=RA*i;
	}
	i=7;
	if((!R[i])&&(!L[i])&&(!P[i])){
		R[i]=L[i]=P[i]=1;
		val+=RA*i;
		dfs(k+1);
		R[i]=L[i]=P[i]=0;
		val-=RA*i;
	}
	i=8;
	if((!R[i])&&(!L[i])&&(!P[i])){
		R[i]=L[i]=P[i]=1;
		val+=RA*i;
		dfs(k+1);
		R[i]=L[i]=P[i]=0;
		val-=RA*i;
	}
	i=9;
	if((!R[i])&&(!L[i])&&(!P[i])){
		R[i]=L[i]=P[i]=1;
		val+=RA*i;
		dfs(k+1);
		R[i]=L[i]=P[i]=0;
		val-=RA*i;
	}
}
int main(){
	freopen("sudoku.in","r",stdin);
	freopen("sudoku.out","w",stdout); 
	for (int i=0;i<=81;i++) mod[i]=i%9,div[i]=i/9;
	for (int i=1;i<=9;i++)
	for (int j=1;j<=9;j++)
		ra[i][j]+=5;
	for(int i=1;i<=9;i++)
	for(int j=1;j<=9;j++){
		scanf("%d",&n);
		if(n){
			r[i][n]=1;
			l[j][n]=1;
			p[g[i][j]][n]=1;
			val+=ra[i][j]*n;
		}
		map[i][j]=n;
	}
	dfs(1);
	if(!ans) printf("-1");else printf("%d",ans);
	return 0;
}