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

#include<iostream>
#include<cstdlib>
#include<cstdio>
#include<cstring>
using namespace std;
int a[12][12],w[12][12],ans=0;
bool hang[12][12],lie[12][12],ge[12][12];
int num[12][12];
void dfs(int x,int y)
{
	//cout<<"x="<<x<<" "<<"y="<<y<<endl;
  if(x==10)
  {
  	int ji=0;
  	for(int i=1;i<=9;++i)
  	  for(int j=1;j<=9;++j)
  	    ji+=w[i][j]*a[i][j];
    ans=max(ans,ji);
    return ;
  }
  if(!a[x][y])
  {
    for(int i=1;i<=9;++i)
      if(!hang[x][i]&&!lie[y][i]&&!ge[num[x][y]][i])
      {
        hang[x][i]=lie[y][i]=ge[num[x][y]][i]=1;
        a[x][y]=i;
        if(y+1>9)
          dfs(x+1,1);
        else
          dfs(x,y+1);
        a[x][y]=0;
        hang[x][i]=lie[y][i]=ge[num[x][y]][i]=0;
      }
  }
  else
  {
    if(y+1>9)
      dfs(x+1,1);
    else
      dfs(x,y+1);
  }
}
int main()
{   
  freopen("sudoku.in","r",stdin);
  freopen("sudoku.out","w",stdout);
  for(int i=9;i>=1;--i)
    for(int j=9;j>=1;--j)
      cin>>a[i][j];
  for(int i=1;i<=9;++i)
    w[1][i]=w[9][i]=w[i][1]=w[i][9]=6;
  for(int i=2;i<=8;++i)
    w[2][i]=w[8][i]=w[i][2]=w[i][8]=7;
  for(int i=3;i<=7;++i)
    w[3][i]=w[7][i]=w[i][3]=w[i][7]=8;
  for(int i=4;i<=6;++i)
    w[4][i]=w[6][i]=w[i][4]=w[i][6]=9;
  w[5][5]=10;
  for(int i=1;i<=3;++i)
    for(int j=1;j<=9;++j)
      num[i][j]=(j-1)/3+1;
  for(int i=4;i<=6;++i)
    for(int j=1;j<=9;++j)
      num[i][j]=(j-1)/3+4;
  for(int i=7;i<=9;++i)
    for(int j=1;j<=9;++j)
      num[i][j]=(j-1)/3+7;
  for(int i=1;i<=9;++i)
    for(int j=1;j<=9;++j)
      if(a[i][j])
      {
        //ans+=a[i][j]*w[i][j];
        hang[i][a[i][j]]=1;
        lie[j][a[i][j]]=1;
        ge[num[i][j]][a[i][j]]=1;
      } 
  dfs(1,1);
  if(ans==0)
    ans=-1;
  cout<<ans;
  return 0;
}