靶形数独

题目描述

小城和小华都是热爱数学的好学生，最近，他们不约而同地迷上了数独游戏，好胜的他们想用数独来一比高低。

但普通的数独对他们来说都过于简单了，于是他们向 Z 博士请教，Z 博士拿出了他最近发明的“靶形数独”，作为这两个孩子比试的题目。

靶形数独的方格同普通数独一样，在 $9 \times 9$ 的大九宫格中有 $9$ 个 $3 \times 3$ 的小九宫格（用粗黑色线隔开的）。

在这个大九宫格中，有一些数字是已知的，根据这些数字，利用逻辑推理，在其他的空格上填入 $1$ 到 $9$ 的数字。

每个数字在每个小九宫格内不能重复出现，每个数字在每行、每列也不能重复出现。

但靶形数独有一点和普通数独不同，即每一个方格都有一个分值，而且如同一个靶子一样，离中心越近则分值越高。

分值分布

靶形数独的分值分布如下（从中心向外）：

• 最里面一格（黄色区域）为 10分
• 黄色区域外面的一圈（红色区域）每个格子为 9分
• 再外面一圈（蓝色区域）每个格子为 8分
• 蓝色区域外面一圈（棕色区域）每个格子为 7分
• 最外面一圈（白色区域）每个格子为 6分

分值矩阵具体如下：

6 6 6 6 6 6 6 6 6
6 7 7 7 7 7 7 7 6
6 7 8 8 8 8 8 7 6
6 7 8 9 9 9 8 7 6
6 7 8 9 10 9 8 7 6
6 7 8 9 9 9 8 7 6
6 7 8 8 8 8 8 7 6
6 7 7 7 7 7 7 7 6
6 6 6 6 6 6 6 6 6

分数计算

总分数是每个方格上的分值和完成这个数独时填在相应格上的数字的乘积的总和。

例如，如果一个格子分值为 $8$，填入了数字 $5$，则该格子得分为 $8 \times 5 = 40$。

比赛要求

每个人必须完成一个给定的数独（每个给定数独可能有不同的填法），而且要争取更高的总分数。

游戏规定，将以总分数的高低决出胜负。

输入格式

输入一共包含 $9$ 行。

每行 $9$ 个整数（每个数都在 $0$—$9$ 的范围内），表示一个尚未填满的数独方格，未填的空格用 $0$ 表示。

每两个数字之间用一个空格隔开。

输出格式

输出可以得到的靶形数独的最高分数。

如果这个数独无解，则输出整数 $-1$。

数据范围

• 40% 的数据，数独中非 $0$ 数的个数不少于 $30$。
• 80% 的数据，数独中非 $0$ 数的个数不少于 $26$。
• 100% 的数据，数独中非 $0$ 数的个数不少于 $24$。

输入样例

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 

输出样例

2829

样例解释

对于给定的输入样例，可以完成如下靶形数独：

7 4 2 9 8 3 5 6 1
1 3 8 4 7 5 9 2 6
5 6 9 2 1 4 3 8 7
8 7 5 1 2 6 4 9 3
9 2 6 3 5 7 1 4 8
4 1 3 8 9 2 7 5 6
6 5 7 4 3 1 2 9 8
2 9 1 7 6 8 5 3 4
3 8 4 5 2 9 6 1 2

根据分值矩阵计算每个格子的得分并求和，可以得到最高分数为 $2829$。

如果该数独无解，则输出 $-1$。

时空限制

• 时间限制：2秒
• 空间限制：64MB