记录编号	462617	评测结果	AAAAAAAAATATAATTAAAA
题目名称	[NOIP 2009]靶形数独	最终得分	80
用户昵称	하루Kiev	是否通过	未通过
代码语言	C++	运行时间	9.639 s
提交时间	2017-10-22 19:17:00	内存使用	0.29 MiB

#include <stdio.h>
#include <algorithm>
#include <cmath>
using namespace std;
int sco[10][10],map[10][10],bl[10][10],sum;
bool h[10][10],l[10][10],g[10][10];
void matrix_init(){
	 for(int i=1;i<=9;i++) sco[1][i]=sco[i][1]=sco[9][i]=sco[i][9]=6;
	 for(int i=2;i<=8;i++) sco[2][i]=sco[i][2]=sco[i][8]=sco[8][i]=7;
	 for(int i=3;i<=7;i++) sco[3][i]=sco[i][3]=sco[i][7]=sco[7][i]=8;
	 for(int i=4;i<=6;i++) sco[4][i]=sco[i][4]=sco[i][6]=sco[6][i]=9;
	 sco[5][5]=10;
	 for(int i=1;i<=3;i++) for(int j=1;j<=3;j++) bl[i][j]=1;
	 for(int i=1;i<=3;i++) for(int j=4;j<=6;j++) bl[i][j]=2;
	 for(int i=1;i<=3;i++) for(int j=7;j<=9;j++) bl[i][j]=3;
	 for(int i=4;i<=6;i++) for(int j=1;j<=3;j++) bl[i][j]=4;
	 for(int i=4;i<=6;i++) for(int j=4;j<=6;j++) bl[i][j]=5;
	 for(int i=4;i<=6;i++) for(int j=7;j<=9;j++) bl[i][j]=6;
	 for(int i=7;i<=9;i++) for(int j=1;j<=3;j++) bl[i][j]=7;
	 for(int i=7;i<=9;i++) for(int j=4;j<=6;j++) bl[i][j]=8;
	 for(int i=7;i<=9;i++) for(int j=7;j<=9;j++) bl[i][j]=9;
	 for(int i=1;i<=9;i++) for(int j=1;j<=9;j++){
	     scanf("%d",&map[i][j]);if(map[i][j]!=0){
		 h[i][map[i][j]]=1; l[j][map[i][j]]=1; g[bl[i][j]][map[i][j]]=1;}}
}	 
void check(){
	 int ans=0;
	 for(int i=1;i<=9;i++)
	     for(int j=1;j<=9;j++)
	         ans+=map[i][j]*sco[i][j];
	 sum=max(sum,ans);
}
void dfs(int x,int y){
	 if(x==10){check();return ;}
	 if(map[x][y]){if(y!=1) dfs(x,y-1);else dfs(x+1,9);return;}
	 for(int i=1;i<=9;i++)
	     if(!g[bl[x][y]][i]&&!h[x][i]&&!l[y][i]){
	        g[bl[x][y]][i]=h[x][i]=l[y][i]=1;map[x][y]=i;
	        if(y!=1) dfs(x,y-1);else dfs(x+1,9);
	        g[bl[x][y]][i]=h[x][i]=l[y][i]=0;map[x][y]=0;
		 }
}
int main(){
	freopen("sudoku.in","r",stdin);
	freopen("sudoku.out","w",stdout);
	matrix_init();
	dfs(1,9);
	if(sum==0) puts("-1");
	else printf("%d",sum);
}
/*
1 0 0 0 5 0 0 9 3
0 0 0 9 1 2 0 0 0
0 0 0 6 0 4 0 0 0
8 6 0 0 0 0 0 0 0
0 0 0 0 6 0 0 0 7
0 0 0 0 0 0 0 0 0
0 0 0 0 4 0 7 0 2
4 2 0 3 8 0 0 0 9
0 0 0 0 0 9 0 3 4
*/