当前位置:首页 > 搜索 > 启发式搜索 > 正文
SSOJ1298靶形数独(NOIP2009)
1503+

题目大意:填数独,不同格子得分不一样;现在告诉你算分数的方法,请问怎样填分数最高?最高分是多少?

题目描述

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

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

上图具体的分值分布是:最里面一格(黄色区域)为 10 分,黄色区域外面的一圈(红色区域)每个格子为 9 分,再外面一圈(蓝色区域)每个格子为 8 分,蓝色区域外面一圈(棕色区域)每个格子为 7 分,最外面一圈(白色区域)每个格子为 6 分,如上图所示。比赛的要求是:每个人必须完成一个给定的数独(每个给定数独可能有不同的填法),而且要争取更高的总分数。而这个总分数即每个方格上的分值和完成这个数独时填在相应格上的数字的乘积的总和。如图,在以下的这个已经填完数字的靶形数独游戏中,总分数为 2829。游戏规定,将以总分数的高低决出胜负。

由于求胜心切,小城找到了善于编程的你,让你帮他求出,对于给定的靶形数独,能够得到的最高分数。

输入输出格式

输入格式:

一共 9 行。每行 9 个整数(每个数都在 0―9 的范围内),表示一个尚未填满的数独方格,未填的空格用“0”表示。每两个数字之间用一个空格隔开。

输出格式:

输出文件 sudoku.out 共 1 行。

输出可以得到的靶形数独的最高分数。如果这个数独无解,则输出整数-1。

输入输出样例

输入样例#1:

sudoku1
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

sudoku2
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

输出样例#1:

sudoku1
2829

sudoku2
2852

说明

【数据范围】

40%的数据,数独中非 0 数的个数不少于 30。

80%的数据,数独中非 0 数的个数不少于 26。

100%的数据,数独中非 0 数的个数不少于 24。

NOIP 2009 提高组 第四题

解题思路

1、预处理分数,并将分数填入二维数组a中,填法很多种,可以找数学规律,也可以一个一个赋值,或者定义的时候赋值;

2、读入数独,同时判断原来的数独是否满去要求,不满足的就输出-1;

3、一个一个空格慢慢填,填的时候判断是否重复;

4、填完后记录最大值,搜索完毕后输出。

难点1:如何判断行列小九宫格的重复数字?

首先是行重复判断,用二维数组记录,x[行][数字]非0则这行该数字填过,否则每天过;列重复判断道理相同;最后是小九宫格,共有9个,用二维数组表示xy[行][列][数字],非0表示该行该列的小九宫格已用过该数字;转换方法:行用0-8来表示,除以3后,刚好对应3行九宫格,列亦如是。

难点2:如何搜索才会更快?

有人说,这道题从前往后搜索,和从后往前搜索,速度很不一样。为什么了?我们想想,如果让你来填,你会怎么填?肯定是找好填的先填!如果某一行、某一列或者某一个小九宫格以及有8个数字了,那么最后那个可以直接确定。搜索也是如此,先搜索好填的,这样相当于剪枝剪前面的。(剪前面的枝比后面的效率高很多,是吧?)

程序实现

About

坚决不Copy代码!

本文标签:,,,,

SSOJ1298靶形数独(NOIP2009):等您坐沙发呢!

发表评论

😉😐😡😈🙂😯🙁🙄😛😳😮mrgreen.png😆💡😀👿😥😎😕

快捷键:Ctrl+Enter