0%

FjnuOJ - 搜索剪枝策略 - 靶形数独

原题:https://fjnuacm.top/d/junior/p/491?tid=633184a5ea0e1b063194593d

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

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

题意

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

铺垫

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

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

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

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

不过需要注意的是,我们没有必要嵌套两个 (你喜欢的话记得 ),只需在传递参数的时候把当前列 即可。

思路

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

这没有错,但你会喜提

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

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

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

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

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

还有一件事,你会如何算这个分数呢?

  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. 整出来一个公式:

对应AC代码

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);
    }
}

好久不玩数独了