杰尼龟刚刚接触了信息学竞赛，有一天它遇到了这样一个题：靶形数独。

“简单！”杰尼龟心想，同时很快就写出了一份程序，可是测试时却出现了错误。

最经典的搜索剪枝

一句话题意

完成一个每格具有分数的数独，使分数和最大。

铺垫

先来看看这题 数独 - 洛谷.

显然，我们只需要用dfs就可以了。

我们传递两个参数，代表当前我们搜索的点。

然后我们判断一下列有没有超出最大值，有的话跳到下一行即可。

不过需要注意的是，我们没有必要嵌套两个for（你喜欢的话记得break），只需在传递参数的时候把当前列+1即可。

思路

首先，我们很容易想到直接套数独的模板，然后记录一下最高分即可。

这没有错，但你会喜提2tle。

为什么呢？你可以试试用你的思维来解数独。

当拿到一个数独的时候，你的第一反应是什么？

没错，自然是从空格最少的行填起。

这里就存在一个剪枝：对行排序。

我们可以用桶排序的方式，记录下排序后下标对应原行的下标即可。

还有一件事，你会如何算这个分数呢？

1.用空间换时间，即数组

int k[10][10]={
	0,0,0,0,0,0,0,0,0,0,
	0,6,6,6,6,6,6,6,6,6,
	0,6,7,7,7,7,7,7,7,6,
	0,6,7,8,8,8,8,8,7,6,
	0,6,7,8,9,9,9,8,7,6,
	0,6,7,8,9,10,9,8,7,6,
	0,6,7,8,9,9,9,8,7,6,
	0,6,7,8,8,8,8,8,7,6,
	0,6,7,7,7,7,7,7,7,6,
	0,6,6,6,6,6,6,6,6,6
};

2.整出来一个公式 10 - max(abs(i - 4), abs(j - 4))

然后就解完力

AC(Java)代码

import java.util.*;

public class Main {

    static int[][] data = new int[10][10];
    static boolean[][] rowVisited = new boolean[10][10],
            columnVisited = new boolean[10][10],
            squareVisited = new boolean[10][10];
    static Integer[] reflectRow = new Integer[9];
    static int ans = -1;

    private static void dfs(int x, int y){
        if(x == 9){
            int now = 0;
            for(int i=0;i<9;i++) for(int j=0;j<9;j++){
                now += data[i][j] * (10 - Math.max(Math.abs(i - 4), Math.abs(j - 4)));
            }
            ans = Math.max(ans, now);
            return;
        }
        if(y == 9){
            dfs(x + 1, 0);
            return;
        }
        int realX = reflectRow[x];
        if(data[realX][y] != 0) dfs(x, y + 1);
        else {
            int squareId = realX / 3 * 3 + y / 3;
            for (int i = 1; i <= 9; i++) {
                if (!rowVisited[realX][i] && !columnVisited[y][i] && !squareVisited[squareId][i]) {
                    rowVisited[realX][i] = true;
                    columnVisited[y][i] = true;
                    squareVisited[squareId][i] = true;
                    data[realX][y] = i;
                    dfs(x, y + 1);
                    rowVisited[realX][i] = false;
                    columnVisited[y][i] = false;
                    squareVisited[squareId][i] = false;
                    data[realX][y] = 0; //好久没写回溯了
                }
            }
        }
    }

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        for(int i=0;i<9;i++) reflectRow[i] = i;
        int[] cnt = new int[9];
        for(int i=0;i<9;i++) for(int j=0;j<9;j++){
            data[i][j] = scanner.nextInt();
            rowVisited[i][data[i][j]] = true;
            columnVisited[j][data[i][j]] = true;
            squareVisited[i / 3 * 3 + j / 3][data[i][j]] = true;
            if(data[i][j] > 0) cnt[i] ++;
        }
        Arrays.sort(reflectRow, (o1, o2) -> cnt[o2] - cnt[o1]);
        dfs(0, 0);
        System.out.println(ans);
    }
}