首页 / 题库

P15002 - 靶形数独

算法入门
通过次数7 提交次数12 内存限制 128MB 时间限制1秒

描述

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

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

 

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

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

输入

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

数据规模:

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

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

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

输出

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

样例

  • 复制
  • 复制
  • 复制
  • 复制

提示

意见反馈

    最多上传3张图片,格式为JPG、PNG、JPEG,单张不超过5MB

    注册

    发送验证码

    密码必须包含数字、字母和特殊字符

    找回密码

    发送验证码

    密码必须包含数字、字母和特殊字符

    运行 ID:67149

    • 测试点1:Accepted
    • 用时:0 ms
    • 内存:288 kb
    • 测试点2:Accepted
    • 用时:0 ms
    • 内存:288 kb
    输入
    203
    输出
    203

    test

    测评信息

    错误.in文件下载

    错误.out文件下载

    运行 ID:67149

    2019-01-24 15:06:36