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

#include<cstdio>
#include<iostream>
#include<queue>
#include<map>
using namespace std;
const int score[10][10]={
    {0,0,0,0,0,0,0,0,0,0},
    {0,6,6,6,6,6,6,6,6,6},
    {0,6,7,7,7,7,7,7,7,6},
    {0,6,7,8,8,8,8,8,7,6},
    {0,6,7,8,9,9,9,8,7,6},
    {0,6,7,8,9,10,9,8,7,6},
    {0,6,7,8,9,9,9,8,7,6},
    {0,6,7,8,8,8,8,8,7,6},   
    {0,6,7,7,7,7,7,7,7,6},
    {0,6,6,6,6,6,6,6,6,6},
};
int v[10][10],A[10][10];
int p[3][10][10];
int ans=-1;
void dfs(int x,int y,int sum){
	if(x==0){
		ans=max(ans,sum);
		return ;
	}
	if(A[x][y]){
		if(y==1)dfs(x-1,9,sum+A[x][y]*score[x][y]);
		else dfs(x,y-1,sum+A[x][y]*score[x][y]);
	}
	else {
		for(int num=1;num<=9;num++)
		if(!p[0][x][num]&&!p[1][y][num]&&!p[2][v[x][y]][num]){
			p[0][x][num]=p[1][y][num]=p[2][v[x][y]][num]=1;
			if(y==1)dfs(x-1,9,sum+num*score[x][y]);
			else dfs(x,y-1,sum+num*score[x][y]);
			p[0][x][num]=p[1][y][num]=p[2][v[x][y]][num]=0;
			
		}
	}
}
int main(){
	freopen("sudoku.in","r",stdin);
	freopen("sudoku.out","w",stdout);
	std::ios::sync_with_stdio(false);
	for(int i=1;i<=9;i++)
	for(int j=1;j<=9;j++){
		cin>>A[i][j];
		if(i<=3&&j<=3)v[i][j]=1;
		else if(i<=3&&j<=6)v[i][j]=2;
		else if(i<=3)v[i][j]=3;
		else if(i<=6&&j<=3)v[i][j]=4;
		else if(i<=6&&j<=6)v[i][j]=5;
		else if(i<=6)v[i][j]=6;
		else if(j<=3)v[i][j]=7;
		else if(j<=6)v[i][j]=8;
		else v[i][j]=9;
		if(A[i][j]){
			p[0][i][A[i][j]]++;
			p[1][j][A[i][j]]++;
			p[2][v[i][j]][A[i][j]]++;
		}
	}
	dfs(9,9,0);
	cout<<ans<<endl;
	return 0;
}