记录编号	464600	评测结果	AAAAAAAAAAAAAAAAAAAA
题目名称	[NOIP 2009]靶形数独	最终得分	100
用户昵称	Shirry	是否通过	通过
代码语言	C++	运行时间	4.066 s
提交时间	2017-10-25 21:25:11	内存使用	1.95 MiB

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
struct poi{int x,y;}p[100];
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},
};
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},
};
int ans,times;
bool vis[9][9],lie[9][9],row[9][9];
void dfs(int res,int now){
	if(!res){ans=max(ans,now);return;}
	if(now+res*9*10<ans)return;
	if(times++>8000000)return;
	for(int i=1;i<=9;i++){
		if(!vis[v[p[res].x][p[res].y]][i]&&!lie[p[res].y][i]&&!row[p[res].x][i]){
			vis[v[p[res].x][p[res].y]][i]=1;
			lie[p[res].y][i]=1,row[p[res].x][i]=1;
			dfs(res-1,now+w[p[res].x][p[res].y]*i);
			vis[v[p[res].x][p[res].y]][i]=0;
			lie[p[res].y][i]=0,row[p[res].x][i]=0;
		}
	}
}
int main(){
	freopen("sudoku.in","r",stdin);
	freopen("sudoku.out","w",stdout);
	int k,tot=0,tmp=0;
	for(int i=0;i<9;i++){
		for(int j=0;j<9;j++){
			scanf("%d",&k);
			if(!k)tot++,p[tot].x=i,p[tot].y=j;
			else{
				tmp+=k*w[i][j];
				vis[v[i][j]][k]=1,lie[j][k]=1,row[i][k]=1;
			}
		}
	}
	dfs(tot,tmp);
	if(!ans)printf("-1\n");
	else printf("%d\n",ans);
	return 0;
}