P1074 靶形数独 - 华师一附中OI组

小城和小华都是热爱数学的好学生，最近，他们不约而同地迷上了数独游戏，好胜的他们想用数独来一比高低。但普通的数独对他们来说都过于简单了，于是他们向 Z 博士请教，Z 博士拿出了他最近发明的“靶形数独”，作为这两个孩子比试的题目。

靶形数独的方格同普通数独一样，在 99 格宽×99 格高的大九宫格中有99 个 33 格宽×33 格高的小九宫格（用粗黑色线隔开的）。在这个大九宫格中，有一些数字是已知的，根据这些数字，利用逻辑推理，在其他的空格上填入 11 到 99的数字。每个数字在每个小九宫格内不能重复出现，每个数字在每行、每列也不能重复出现。但靶形数独有一点和普通数独不同，即每一个方格都有一个分值，而且如同一个靶子一样，离中心越近则分值越高。（如图）

上图具体的分值分布是：最里面一格（黄色区域）为 1010 分，黄色区域外面的一圈（红色区域）每个格子为99分，再外面一圈（蓝色区域）每个格子为88 分，蓝色区域外面一圈（棕色区域）每个格子为77分，最外面一圈（白色区域）每个格子为66分，如上图所示。比赛的要求是：每个人必须完成一个给定的数独（每个给定数独可能有不同的填法），而且要争取更高的总分数。而这个总分数即每个方格上的分值和完成这个数独时填在相应格上的数字的乘积的总和

#include<algorithm>
#include<iostream>
#include<cstdlib>
#include<cstdio>
#include<string>
#include<cmath>
using namespace std;
#define FOR(i,a,b) for(register int i=a;i<=b;++i)
#define For(i,a,b) for(register int i=a;i>=b;--i)
typedef long long ll;
int a[10][10],c[10],ran[30],ur,uc,ans,uh,aa[10][10],cc;
bool b1[10][10],b2[10][10],b3[10][10];
bool cmp(int x,int y){return c[x]<c[y];}
bool flag=0;
void pre()
{
FOR(i,1,9) FOR(j,1,9) scanf("%d",&a[i][j]);
FOR(i,1,9) c[i]=9;
FOR(i,1,9) FOR(j,1,9) if(a[i][j])
{
c[i]--;
b1[i][a[i][j]]=1;
b2[j][a[i][j]]=1;
b3[((i-1)/3)*3+(j-1)/3+1][a[i][j]]=1;
cc+=a[i][j]*(10-max(abs(i-5),abs(j-5)));
}
FOR(i,1,9) ran[i]=i;
sort(ran+1,ran+10,cmp);
}
void dfs(int x)
{
if(x==82) {ans=max(ans,cc);flag=1;return;}
int ur=ran[(x-1)/9+1];int uc=(x-1)%9+1;int uh=((ur-1)/3)*3+(uc-1)/3+1;
if(a[ur][uc]) dfs(x+1);
else FOR(i,1,9) if((!b1[ur][i]) && (!b2[uc][i]) && (!b3[uh][i]))
{
cc+=i*(10-max(abs(ur-5),abs(uc-5)));
b1[ur][i]=b2[uc][i]=b3[uh][i]=1;
dfs(x+1);
cc-=i*(10-max(abs(ur-5),abs(uc-5)));
b1[ur][i]=b2[uc][i]=b3[uh][i]=0;
}
}
int main()
{
pre();
dfs(1);
if(flag) printf("%d",ans);
else printf("-1");
return 0;
}

复制代码