难度：提高+/省选-

题目描述

        小城和小华都是热爱数学的好学生，最近，他们不约而同地迷上了数独游戏，好胜的他们想用数独来一比高低。但普通的数独对他们来说都过于简单了，于是他们向 Z 博士请教，Z 博士拿出了他最近发明的“靶形数独”，作为这两个孩子比试的题目。
        靶形数独的方格同普通数独一样，在9格宽×9格高的大九宫格中有9个3格宽×3格高的小九宫格(用粗黑色线隔开的)。在这个大九宫格中，有一些数字是已知的，根据这些数字，利用逻辑推理，在其他的空格上填入 1 到 9的数字。每个数字在每个小九宫格内不能重复出现，每个数字在每行，每列也不能重复出现。但靶形数独有一点和普通数独不同，即每一个方格都有一个分值，而且如同一个靶子一样，离中心越近则分值越高。

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

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

输入输出格式

输入格式:

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

输出格式:

        输出共 1 行。输出可以得到的靶形数独的最高分数。如果这个数独无解，则输出整数-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

Sample output#1

2829

Sample input#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#2

2852

题解

        考察深度优先搜索(DFS)，有一定难度。
        一个基本思路是，从首行首列开始进行DFS，将未填数的格子填上数。在填数过程中要注意符合数独的规则，也就是说要开数组记录当前行当前列和当前九宫格已有数字的情况。
        按照这种方法，在填完末行末列的格子时，整个数独已经填好且符合规则。此时计算数独的分数，记录分数最大值。这里可以开一个常量数组记录每个格子的分数以简化运算。
        另一个值得注意的是，倘若首行待填格很多，则可能会导致DFS频繁向底层回溯，加大函数调用次数，很容易导致TLE。一种解决方法是从待填格最少的行开始DFS，将待填格最多的行后置，这样DFS向底层回溯的次数会减小，高层回溯次数增加，能够提高效率。

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
#include<iostream>

#define ID(x, y) x/3*3+y/3+1
using namespace std;
const int Point[9][9] = {{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}};
int row[9][10] = {0}, colum[9][10] = {0}, form[10][10] = {0};
int op[9][9], rank2[10];
int temp[9];
int ans = -1;

void calculate() {
    int sum = 0;
    for (int i = 0; i < 9; i++)
        for (int j = 0; j < 9; j++)sum += op[i][j] * Point[i][j];
    ans = max(ans, sum);
}

void DFS(int x, int y, int r) {
    if (y == 9) {
        if (r < 8)
            DFS(rank2[r + 1], 0, r + 1);
        else calculate();
        return;
    }
    if (op[x][y]) {
        DFS(x, y + 1, r);
        return;
    }
    for (int i = 1; i <= 9; i++) {
        if (row[x][i] || colum[y][i] || form[ID(x, y)][i])continue;
        row[x][i] = colum[y][i] = form[ID(x, y)][i] = 1;
        op[x][y] = i;
        DFS(x, y + 1, r);
        op[x][y] = 0;
        row[x][i] = colum[y][i] = form[ID(x, y)][i] = 0;
    }
}

int main() {
    for (int i = 0; i < 9; i++) {
        temp[i] = i * 10 + 9;
        for (int j = 0; j < 9; j++) {
            cin >> op[i][j];
            if (op[i][j])
                row[i][op[i][j]] = colum[j][op[i][j]] = form[ID(i, j)][op[i][j]]
                        = 1, temp[i]--;
        }
    }
    for (int i = 8; i >= 0; i--)
        for (int j = 0; j < i; j++)
            if (temp[j] % 10 > temp[j + 1] % 10)swap(temp[j], temp[j + 1]);
    for (int i = 0; i < 9; i++)rank2[i] = temp[i] / 10;
    DFS(rank2[0], 0, 0);
    cout << ans;
    return 0;
}