NOIP2009靶形数独
题目描述 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 0
0 0 0 2 0 0 0 8 0
0 0 5 0 2 0 0 0 3
0 0 0 0 0 0 6 4 8
4 1 3 0 0 0 0 0 0
0 0 7 0 0 2 0 9 0
2 0 1 0 6 0 8 0 4
0 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 0
7 4 0 0 0 5 0 1 0
1 9 5 0 8 0 0 0 0
0 7 0 0 0 0 0 2 5
0 3 0 5 7 9 1 0 8
0 0 0 6 0 1 0 0 0
0 6 0 9 0 0 0 0 1
0 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。
代码
裸搜索在codevs80分，而在vijos上加卡时才能获得75分
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 |
#include<iostream> #include<cstdio> #include<ctime> #define searchnext(x,y) y==9? search(x+1,1):search(x,y+1) using namespace std; bool r[10][10],l[10][10],s[10][10];//行，列，小九宫格 int a[10][10],b[10][10]; int ans=-1,score; int getscore(int x,int y,int k) { if(x==5&&y==5)return 10*k; else if(x>=4&&x<=6&&y>=4&&y<=6)return 9*k; else if(x>=3&&x<=7&&y>=3&&y<=7)return 8*k; else if(x>=2&&x<=8&&y>=2&&y<=8)return 7*k; else return 6*k; } bool fillin(int x,int y,int k) { if(r[x][k])return 0; if(l[y][k])return 0; if(s[(x-1)/3*3+(y-1)/3+1][k])return 0; b[x][y]=k; r[x][k]=l[y][k]=s[(x-1)/3*3+(y-1)/3+1][k]=1; score+=getscore(x,y,k); return 1; } void del(int x,int y,int k) { b[x][y]=0; r[x][k]=l[y][k]=s[(x-1)/3*3+(y-1)/3+1][k]=0; } void search(int x,int y) { if(clock()>1000)return; if(x==10&y==1){ ans=max(ans,score); return;} if(b[x][y])searchnext(x,y); else for(int i=1;i<=9;i++) { int t=score; if(fillin(x,y,i)) { searchnext(x,y); del(x,y,i); score=t; } } } int main() { for(int i=1;i<=9;i++) for(int j=1;j<=9;j++) { scanf("%d",&a[i][j]); if(a[i][j])fillin(i,j,a[i][j]); } search(1,1); printf("%d",ans); return 0; } |
倒过来搜索（把输入倒过来…）快多了直接AC，但是在vijos可能还需要卡时。。。
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 |
#include<iostream> #include<cstdio> #define searchnext(x,y) y==9? search(x+1,1):search(x,y+1) using namespace std; bool r[10][10],l[10][10],s[10][10];//行，列，小九宫格 int a[10][10],b[10][10]; int ans=-1,score; int getscore(int x,int y,int k) { if(x==5&&y==5)return 10*k; else if(x>=4&&x<=6&&y>=4&&y<=6)return 9*k; else if(x>=3&&x<=7&&y>=3&&y<=7)return 8*k; else if(x>=2&&x<=8&&y>=2&&y<=8)return 7*k; else return 6*k; } bool fillin(int x,int y,int k) { if(r[x][k])return 0; if(l[y][k])return 0; if(s[(x-1)/3*3+(y-1)/3+1][k])return 0; b[x][y]=k; r[x][k]=l[y][k]=s[(x-1)/3*3+(y-1)/3+1][k]=1; score+=getscore(x,y,k); return 1; } void del(int x,int y,int k) { b[x][y]=0; r[x][k]=l[y][k]=s[(x-1)/3*3+(y-1)/3+1][k]=0; } void search(int x,int y) { if(x==10&y==1){ ans=max(ans,score); return;} if(b[x][y])searchnext(x,y); else for(int i=1;i<=9;i++) { int t=score; if(fillin(x,y,i)) { searchnext(x,y); del(x,y,i); score=t; } } } int main() { for(int i=9;i>0;i--) for(int j=9;j>0;j--) { scanf("%d",&a[i][j]); if(a[i][j])fillin(i,j,a[i][j]); } search(1,1); printf("%d",ans); return 0; } |
再加一点无聊的，更快。。
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 |
#include<iostream> #include<cstdio> #define searchnext(x,y) y==9? search(x+1,1):search(x,y+1) using namespace std; bool r[10][10],l[10][10],s[10][10];//行，列，小九宫格 int a[10][10],b[10][10]; int getscore[10][10][10]; int ans=-1,score; int culscore(int x,int y,int k) { if(x==5&&y==5)return 10*k; else if(x>=4&&x<=6&&y>=4&&y<=6)return 9*k; else if(x>=3&&x<=7&&y>=3&&y<=7)return 8*k; else if(x>=2&&x<=8&&y>=2&&y<=8)return 7*k; else return 6*k; } bool fillin(int x,int y,int k) { if(r[x][k]||l[y][k]||s[(x-1)/3*3+(y-1)/3][k])return 0; b[x][y]=k; r[x][k]=l[y][k]=s[(x-1)/3*3+(y-1)/3][k]=1; score+=getscore[x][y][k]; return 1; } void del(int x,int y,int k) { r[x][k]=l[y][k]=s[(x-1)/3*3+(y-1)/3][k]=0; } void search(int x,int y) { if(x==10&y==1){ ans=max(ans,score); return;} if(b[x][y])searchnext(x,y); else { for(int i=1;i<=9;i++) { int t=score; if(fillin(x,y,i)) { searchnext(x,y); del(x,y,i); score=t; } } b[x][y]=0; } } int main() { for(int i=1;i<=9;i++) for(int j=1;j<=9;j++) for(int k=1;k<=9;k++) getscore[i][j][k]=culscore(i,j,k); for(int i=9;i>0;i--) for(int j=9;j>0;j--) { scanf("%d",&a[i][j]); if(a[i][j])fillin(i,j,a[i][j]); } search(1,1); printf("%d",ans); return 0; } |
或者可以换一种思路，剪枝
当剩余的数字*9加上当前的分数小于答案就返回
但是还是超时了什么心态！！不管了！
出题人故意卡按顺序搜索，所以双向或者从另外三个角开始搜就可以了
OI 课件=>
vijos数据良心何在？