记录编号	141187	评测结果	AAAAAAAAAAAAAAAAAATA
题目名称	[NOIP 2009]靶形数独	最终得分	95
用户昵称	天一阁	是否通过	未通过
代码语言	C++	运行时间	2.877 s
提交时间	2014-11-30 08:04:07	内存使用	0.32 MiB

#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
struct node{int x,y,w;}V[101]={0};
int v[9][9]={
	{1,1,1,2,2,2,3,3,3},
	{1,1,1,2,2,2,3,3,3},
	{1,1,1,2,2,2,3,3,3},
	{4,4,4,5,5,5,6,6,6},
	{4,4,4,5,5,5,6,6,6},
	{4,4,4,5,5,5,6,6,6},
	{7,7,7,8,8,8,9,9,9},
	{7,7,7,8,8,8,9,9,9},
	{7,7,7,8,8,8,9,9,9}
},x,ans=-1,tim=0;
int w[9][9]={
	{6,6,6,6,6,6,6,6,6},
	{6,7,7,7,7,7,7,7,6},
	{6,7,8,8,8,8,8,7,6},
	{6,7,8,9,9,9,8,7,6},
	{6,7,8,9,10,9,8,7,6},
	{6,7,8,9,9,9,8,7,6},
	{6,7,8,8,8,8,8,7,6},
	{6,7,7,7,7,7,7,7,6},
	{6,6,6,6,6,6,6,6,6}
},tot=0;
bool vis[10][10]={0},lx[10][10]={0},rx[10][10]={0};
void dfs(int t,int now){
	if(!t){ans=max(ans,now);return;}
	for(int i=1;i<=9;i++){
		if(!vis[v[V[t].x][V[t].y]][i]&&!lx[V[t].x][i]&&!rx[V[t].y][i]){
			vis[v[V[t].x][V[t].y]][i]=true;
			lx[V[t].x][i]=true;
			rx[V[t].y][i]=true;
			dfs(t-1,now+w[V[t].x][V[t].y]*i);
			vis[v[V[t].x][V[t].y]][i]=false;
			lx[V[t].x][i]=false;
			rx[V[t].y][i]=false;
		}
	}
}
int main(){
	freopen("sudoku.in","r",stdin);
	freopen("sudoku.out","w",stdout);
	int sta=0;
	for(int i=0;i<9;i++)
		for(int j=0;j<9;j++){
			cin>>x;
			if(!x){V[++tot].x=i;V[tot].y=j;}
			else{
				sta+=x*w[i][j];
				vis[v[i][j]][x]=true;
				lx[i][x]=true;
				rx[j][x]=true;
			}
		}
	dfs(tot,sta);
	cout<<ans<<endl;
}