蓝桥杯方格填数

素颜马尾好姑娘i 2022-03-08 13:08 275阅读 0赞

如图，如下的10个格子，填入0~9的数字。要求：连续的两个数字不能相邻。
    （左右、上下、对角都算相邻）一共有多少种可能的填数方案？
    请填写表示方案数目的整数。

![20190315113244642.jpg][]

1.判断8个方向相减绝对值是否为1，不为1的话则判断这个数是否使用过！

2.到最后一列，要换行

3.到最后一个元素，递归终止，同时sum++

public class Main {
    	public static int[][] a;
    	public static int[] v = new int[10];
    	public static int sum = 0;
    
    	public static void main(String[] args) {
    		a = new int[3][4];
    		for (int i = 0; i < 3; i++) {
    			for (int j = 0; j < 4; j++) {
    				a[i][j] = -9;
    			}
    		}
    		f(0, 1);
    		System.out.println(sum);
    	}
    
    	private static void f(int i, int j) {
    		// TODO 自动生成的方法存根
    		if (i == 2 && j == 3) {
    			sum++;
    			return;
    		}
    		for (int k = 0; k <= 9; k++) {
    			if (judge(k, i, j) == 1 && v[k] == 0) {
    				a[i][j] = k;
    				v[k] = 1;
    				if (j == 3) {
    					f(i + 1, 0);// 换行
    				} else {
    					f(i, j + 1);
    				}
    				v[k] = 0;
    				a[i][j] = -9;
    			}
    		}
    	}
    
    	private static int judge(int k, int i, int j) {
    		// TODO 自动生成的方法存根
    		if (i - 1 >= 0 && (a[i - 1][j] == k + 1 || a[i - 1][j] == k - 1)) {// 上
    			return 0;
    		} else if (i + 1 <= 2 && (a[i + 1][j] == k + 1 || a[i + 1][j] == k - 1)) {// 下
    			return 0;
    		} else if (j - 1 >= 0 && (a[i][j - 1] == k + 1 || a[i][j - 1] == k - 1)) {// 左
    			return 0;
    		} else if (j + 1 <= 3 && (a[i][j + 1] == k + 1 || a[i][j + 1] == k - 1)) {// 右
    			return 0;
    		} else if (i - 1 >= 0 && j - 1 >= 0 && (a[i - 1][j - 1] == k + 1 || a[i - 1][j - 1] == k - 1)) {// 左上
    			return 0;
    		} else if (i + 1 <= 2 && j + 1 <= 3 && (a[i + 1][j + 1] == k + 1 || a[i + 1][j + 1] == k - 1)) {// 右下
    			return 0;
    		} else if (i - 1 >= 0 && j + 1 <= 3 && (a[i - 1][j + 1] == k + 1 || a[i - 1][j + 1] == k - 1)) {// 右上
    			return 0;
    		} else if (i + 1 <= 2 && j - 1 >= 0 && (a[i + 1][j - 1] == k + 1 || a[i + 1][j - 1] == k - 1)) {// 左下
    			return 0;
    		}
    		return 1;
    	}
    }

[20190315113244642.jpg]: /images/20220308/e9e2266372d54ab88424e4d1bd456ae4.png