1174 靶形数独
2009年NOIP全国联赛提高组
时间限制: 4 s
空间限制: 128000 KB
题目等级 : 钻石 Diamond
查看运行结果
题目描述 Description
小城和小华都是热爱数学的好学生，最近，他们不约而同地迷上了数独游戏，好胜的他
们想用数独来一比高低。但普通的数独对他们来说都过于简单了，于是他们向Z 博士请教，Z 博士拿出了他最近发明的“靶形数独”，作为这两个孩子比试的题目。靶形数独的方格同普通数独一样，在 9 格宽×9 格高的大九宫格中有9 个3 格宽×3 格高的小九宫格（用粗黑色线隔开的）。在这个大九宫格中，有一些数字是已知的，根据这些数字，利用逻辑推理，在其他的空格上填入1 到9 的数字。每个数字在每个小九宫格内不能
重复出现，每个数字在每行、每列也不能重复出现。但靶形数独有一点和普通数独不同，即每一个方格都有一个分值，而且如同一个靶子一样，离中心越近则分值越高。
上图具体的分值分布是：最里面一格（黄色区域）为 10 分，黄色区域外面的一圈（红
色区域）每个格子为9 分，再外面一圈（蓝色区域）每个格子为8 分，蓝色区域外面一圈（棕色区域）每个格子为7 分，最外面一圈（白色区域）每个格子为6 分，如上图所示。比赛的要求是：每个人必须完成一个给定的数独（每个给定数独可能有不同的填法），而且要争取更高的总分数。而这个总分数即每个方格上的分值和完成这个数独时填在相应格上的数字的乘积的总和。如图，在以下的这个已经填完数字的靶形数独游戏中，总分数为2829。游戏规定，将以总分数的高低决出胜负。由于求胜心切，小城找到了善于编程的你，让你帮他求出，对于给定的靶形数独，能
够得到的最高分数。
输入描述 Input Description
一共 9 行。每行9 个整数（每个数都在0—9 的范围内），表示一个尚未填满的数独方
格，未填的空格用“0”表示。每两个数字之间用一个空格隔开。 输出描述 Output Description
输出可以得到的靶形数独的最高分数。如果这个数独无解，则输出整数-1。
样例输入 Sample Input
【输入输出样例 1】
7 0 0 9 0 0 0 0 1
1 0 0 0 0 5 9 0 00 0 0 2 0 0 0 8 00 0 5 0 2 0 0 0 30 0 0 0 0 0 6 4 84 1 3 0 0 0 0 0 00 0 7 0 0 2 0 9 02 0 1 0 6 0 8 0 40 8 0 5 0 4 0 1 2【输入输出样例 2】
0 0 0 7 0 2 4 5 3
9 0 0 0 0 8 0 0 07 4 0 0 0 5 0 1 01 9 5 0 8 0 0 0 00 7 0 0 0 0 0 2 50 3 0 5 7 9 1 0 80 0 0 6 0 1 0 0 00 6 0 9 0 0 0 0 10 0 0 0 0 0 0 0 6 样例输出 Sample Output
【输入输出样例 1】
2829
【输入输出样例 1】
2852
数据范围及提示 Data Size & Hint
【数据范围】
40%的数据，数独中非0 数的个数不少于30。80%的数据，数独中非0 数的个数不少于26。100%的数据，数独中非0 数的个数不少于24。采用倒着填的方式，一个方格一个方格地填，若有初始值则填下一个，没有则找个符合规则的数填上。
以前写了一个代码，是当前的方格没有数的时候才填数，但不知道为什么答案不对，望大神指点。
#include#include #define M 10using namespace std;int fen[M][M]={ { 0,0,0,0,0,0,0,0,0,0}, { 0,6,6,6,6,6,6,6,6,6}, { 0,6,7,7,7,7,7,7,7,6}, { 0,6,7,8,8,8,8,8,7,6}, { 0,6,7,8,9,9,9,8,7,6}, { 0,6,7,8,9,10,9,8,7,6}, { 0,6,7,8,9,9,9,8,7,6}, { 0,6,7,8,8,8,8,8,7,6}, { 0,6,7,7,7,7,7,7,7,6}, { 0,6,6,6,6,6,6,6,6,6}};int map[M][M],f[M][M],vish[M][M],visl[M][M],visg[4][4][M],ans,tot;void init(int x,int y,int v){ vish[x][v]=1; visl[y][v]=1; visg[(x+2)/3][(y+2)/3][v]=1;}void init2(int x,int y,int v){ vish[x][v]=0; visl[y][v]=0; visg[(x+2)/3][(y+2)/3][v]=0;}void dfs(int x,int y){ if(y<1) { y=9; x--; } if(!x) { ans=max(ans,tot); return; } if(!f[x][y]) { for(int k=1;k<=9;k++) { if(!vish[x][k]&!visl[y][k]&&!visg[(x+2)/3][(y+2)/3][k]) { map[x][y]=k;//赋值 init(x,y,k);//标志 tot+=fen[x][y]*k;//累加分数 dfs(x,y-1); map[x][y]=0; tot-=fen[x][y]*k; init2(x,y,k); } } } else dfs(x,y-1);}int main(){ for(int i=1;i<=9;i++) for(int j=1;j<=9;j++) { scanf("%d",&map[i][j]); if(map[i][j]) { f[i][j]=1; tot+=map[i][j]*fen[i][j]; init(i,j,map[i][j]); } } dfs(9,9); if(ans)printf("%d",ans); else printf("-1"); return 0; }
下面是以前的代码：
#include#include #define M 10using namespace std;int fen[M][M]={ { 0,0,0,0,0,0,0,0,0,0}, { 0,6,6,6,6,6,6,6,6,6}, { 0,6,7,7,7,7,7,7,7,6}, { 0,6,7,8,8,8,8,8,7,6}, { 0,6,7,8,9,9,9,8,7,6}, { 0,6,7,8,9,10,9,8,7,6}, { 0,6,7,8,9,9,9,8,7,6}, { 0,6,7,8,8,8,8,8,7,6}, { 0,6,7,7,7,7,7,7,7,6}, { 0,6,6,6,6,6,6,6,6,6}};int map[M][M],f[M][M],vish[M][M],visl[M][M],visg[4][4][M],ans=0;void init(int x,int y,int v){ vish[x][v]=1; visl[y][v]=1; visg[(x+2)/3][(y+2)/3][v]=1;}void init2(int x,int y,int v){ vish[x][v]=0; visl[y][v]=0; visg[(x+2)/3][(y+2)/3][v]=0;}int ok(){ for(int i=1;i<=9;i++) for(int j=1;j<=9;j++) if(!map[i][j])return 0; return 1;}void dfs(int x,int y,int t){ if(map[x][y])return; if(ok()) { ans=max(t,ans); return; } for(int k=1;k<=9;k++) { if(!vish[x][k]&!visl[y][k]&&!visg[(x+2)/3][(y+2)/3][k]) { map[x][y]=k;//赋值 init(x,y,k);//标志 t+=fen[x][y]*k;//累加分数 int ff=0; for(int i=x;i<=9;i++) { for(int j=y;j<=9;j++) if(!f[i][j]) { dfs(i,j,t);//递归下一个数 map[x][y]=0; init2(x,y,k);//回溯 ff=1; break; } if(ff)break; } } } }int main(){ freopen("jh.in","r",stdin); int tot=0; for(int i=1;i<=9;i++) for(int j=1;j<=9;j++) { scanf("%d",&map[i][j]); if(map[i][j])f[i][j]=1; tot+=map[i][j]*fen[i][j]; init(i,j,map[i][j]); } int flag=0; for(int i=1;i<=9;i++) { for(int j=1;j<=9;j++) if(!f[i][j]) { flag=1; dfs(i,j,tot); break; } if(flag)break; } printf("%d",ans); return 0; }