转载

第七届蓝桥杯Java B——方格填数

如下的10个格子

第七届蓝桥杯Java B——方格填数

填入0~9的数字。要求：连续的两个数字不能相邻。

（左右、上下、对角都算相邻）

一共有多少种可能的填数方案？

public class Main {

    static boolean[] book = new boolean[10];
    static int[][] map = new int[3][4];
    static int ans;

    public static void main(String[] args) {
        map[0][0] = map[2][3] = -2;
        dfs(0, 1);
        System.out.println(ans);
    }

    static void dfs(int x, int y) {
        if (map[x][y] == -2) {
                ans++;
        } else {
            for (int i = 0; i <= 9; i++) {
                if (!book[i] && check(i, x, y)) {
                    book[i] = true;
                    map[x][y] = i;
                    dfs(x + (y + 1 == 4 ? 1 : 0), (y + 1) % 4);
                    book[i] = false;
                }
            }
        }
    }

    static boolean check(int i, int x, int y) {
        if (y - 1 >= 0 && Math.abs(map[x][y - 1] - i) == 1) // left
            return false;
        if (x - 1 >= 0 && Math.abs(map[x - 1][y] - i) == 1) // up
            return false;
        if (x - 1 >= 0 && y - 1 >= 0 && Math.abs(map[x - 1][y - 1] - i) == 1) // leftUp
            return false;
        if (x - 1 >= 0 && y + 1 < 4 && Math.abs(map[x - 1][y + 1] - i) == 1) // RightUp
            return false;
        return true;
    }
}

原文 https://www.wmathor.com/index.php/archives/1270/

正文到此结束