【NOIP1999 提高组T4】 靶形数独

#include<bits/stdc++.h>
using namespace std;
struct countxy{
	int rank,sum;
}data[10];
int x[10][10],y[10][10],all[10][10],a[10][10],s[100][4];
int u,maxans=-1,nowscore;
int getpoint_DJX(int i,int j){
	if(i==1 or j==1 or i==9 or j==9)return 6;
	else if(i==2 or j==2 or i==8 or j==8)return 7;
	else if(i==3 or j==3 or i==7 or j==7)return 8;
	else if(i==4 or j==4 or i==6 or j==6)return 9;
	else return 10;
}
bool cmp(countxy a,countxy b){
	return a.sum<b.sum; 
}
int getpoint_xy(int i,int j){
	if(i<=3){
		if(j<=3)return 1;
		else if(j<=6)return 2;
		else return 3;
	}
	else if(i<=6){
		if(j<=3)return 4;
		else if(j<=6)return 5;
		else return 6;
	}
	else{
		if(j<=3)return 7;
		else if(j<=6)return 8;
		else return 9;
	}
}
void dfs(int p,int score){
	if(p==u){
		if(score>maxans)maxans=score;
		return;
	}
	for(int i=1;i<=9;i++){
		if(!x[s[p][0]][i] and !y[s[p][1]][i] and !all[s[p][3]][i]){
			x[s[p][0]][i]=y[s[p][1]][i]=all[s[p][3]][i]=1;
			dfs(p+1,score+(s[p][2]*i));
			x[s[p][0]][i]=y[s[p][1]][i]=all[s[p][3]][i]=0;
		}
	}
}
void Init(){
	freopen("sudoku.in","r",stdin);
	freopen("sudoku.out","w",stdout);
	for(int i=1;i<=9;i++){
		data[i].rank=i;
	}
}
void ReadData(){
	for(int i=1;i<=9;i++){
		for(int j=1;j<=9;j++){
			scanf("%d",&a[i][j]);
			if(a[i][j]>0){
				nowscore+=a[i][j]*getpoint_DJX(i,j);
				x[i][a[i][j]]=y[j][a[i][j]]=all[getpoint_xy(i,j)][a[i][j]]=1;
			}
			else data[i].sum++;
		}
	}
	sort(data+1,data+10,cmp);
}
void OutPutAns(){
	printf("%d",maxans);
}
void Work(){
	for(int i=1;i<=9;i++){
		for(int j=1;j<=9;j++){
			if(a[data[i].rank][j]==0){
				s[u][0]=data[i].rank,s[u][1]=j;
				s[u][2]=getpoint_DJX(data[i].rank,j);
				s[u++][3]=getpoint_xy(data[i].rank,j);
			}
		}
	}
}
void Search(){
	dfs(0,nowscore);
}
int main(){
	Init();
	ReadData();
	Work();
	Search();
	OutPutAns();
	return 0;
}