java算法 第七届 蓝桥杯B组(题+答案) 6.方格填数

时间:2021-03-03 11:26:16

6.方格填数  (结果填空)

如下的10个格子
java算法 第七届 蓝桥杯B组(题+答案) 6.方格填数

(如果显示有问题,也可以参看【图1.jpg】)


填入0~9的数字。要求:连续的两个数字不能相邻。
(左右、上下、对角都算相邻)


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


请填写表示方案数目的整数。
注意:你提交的应该是一个整数,不要填写任何多余的内容或说明性文字。

提示:和前面第4题分小组,都是用的全排列的思想,只是这个附加了条件,在递归出口时多加一下题目里的附加条件

思路:将表格从上到下从左到右从0开始编号 ,判断每种相邻的方案是否为连续数字,不是则+1

 1 public class _6方格填数 {
 2    public static void main(String[] args) {
 3 //      char[] str={'0','1','2','3','4','5','6','7','8','9'};
 4       char[] str="0123456789".toCharArray();
 5       paixu(str, 0, str.length-1);
 6       System.out.println(count);
 7    }
 8    public static int count=0;
 9    //交换位置
10    public static void swap(char[] c,int i,int j){
11        char temp = c[i];
12        c[i] = c[j];
13        c[j] = temp;
14    }
15    //排序
16    public static void paixu(char[] c,int from,int to){
17        if (to<=1) {
18            return;
19        }if (from == to) {
20            if (check(c)) {
21               count++;    
22            }
23        }else{
24            for (int i = from; i <= to; i++) {
25               swap(c, i, from);
26               paixu(c, from+1, to);
27               swap(c, from, i);
28            }
29        }
30    }
31 //   检查左右,上下,对角不是相邻的数字
32     public static boolean check(char[] c) {
33         if (check2(c[0], c[1]) && check2(c[0], c[3]) && check2(c[0], c[4])&& check2(c[0], c[5])
34             && check2(c[1], c[2])&& check2(c[1], c[4])&& check2(c[1], c[5])&& check2(c[1], c[6])
35             && check2(c[2], c[5])&& check2(c[2], c[6])
36             && check2(c[3], c[4])&& check2(c[3], c[7])&& check2(c[3], c[8])
37             && check2(c[4], c[5])&& check2(c[4], c[7])&& check2(c[4], c[8])&& check2(c[4], c[9])
38             && check2(c[5], c[6])&& check2(c[5], c[8])&& check2(c[5], c[9])
39             && check2(c[6], c[9])
40             && check2(c[7], c[8])
41             && check2(c[8], c[9])) {
42            return true;
43         }
44         return false;
45     }
46 //    检查相邻的数字
47     public static boolean check2(char a,char b){
48         if (a == (b+1)||a==(b-1)) {
49             return false;
50         }
51         return true;
52     }
53 }

运行结果:1580