第七届蓝桥杯javaB组真题解析-方格填数（第六题）

题目

/*

方格填数

如下的10个格子

   +--+--+--+

   |  |  |  |

+--+--+--+--+

|  |  |  |  |

+--+--+--+--+

|  |  |  |

+--+--+--+

（如果显示有问题，也可以参看【图1.jpg】）

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

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

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

请填写表示方案数目的整数。

注意：你提交的应该是一个整数，不要填写任何多余的内容或说明性文字。*/

答案

1580

代码

 public class Main {

     static int sum = 0 ;

     public static void main(String[] args) {

         int a[] = {0,1,2,3,4,5,6,7,8,9};

         int b[] = new int[10];

         String s = "";

         f(a,b,0,s);

         System.out.println(sum);

     }

     private static void f(int[] a,int[] b,int k,String s) {

         if(k!=0 && k!=1 && k!=4 && k!=8 ){

             if(Math.abs(b[k-1]-b[k-2])==1) return;

         }

         if(k>=4 && k<=10 && k!=7){

             if(Math.abs(b[k-1]-b[k-4])==1) return;

         }

         if(k>=5 && k<=10){

             if(Math.abs(b[k-1]-b[k-5])==1) return;

         }

         if(k==6 || k==7 || k==9 || k==10){

             if(Math.abs(b[k-1]-b[k-6])==1) return;

         }

         if(k==a.length) {

             sum++;

             System.out.println(s);

             return;

         }

         for(int i=0;i<a.length;i++){

             String ss = s;

             if(a[i]==-1) continue;

             b[k] = a[i];

             ss += a[i];

             a[i] = -1;

             f(a,b,k+1,ss);

             a[i] = b[k];

         }

     }

 }

分析

　　这又是一道涉及到排列组合的算法题，我用的是比较简单和常见的解法，利用循环递归，开始依次向方格里面填数, 每填一个数都会判断一下这个数是不是符合条件，如果符合条件则递归进去填下一个，如果不符合条件则return，当满足在满足条件的情况下数填完之后（k==10），则sum++，计数加一

　　因为判断条件对方格有所依赖，所以想在短时间内写出一个比较完美通用的算法是有点困难的，我们可以把情况细分，使得条件结构更清晰一点，

　　再说一个我觉得比较有创意的一点，这也是我最近学到的，就是用一个字符串，让这个字符串也参与递归，就可以巧妙的可以把每次的情况都输出来了，我很喜欢。

private static void f(int[] a,int[] b,int k,String s) {

11         if(k!=0 && k!=1 && k!=4 && k!=8 ){

12             if(Math.abs(b[k-1]-b[k-2])==1) return;

13         }

14         if(k>=4 && k<=10 && k!=7){

15             if(Math.abs(b[k-1]-b[k-4])==1) return;

16         }

17         if(k>=5 && k<=10){

18             if(Math.abs(b[k-1]-b[k-5])==1) return;

19         }

20         if(k==6 || k==7 || k==9 || k==10){

21             if(Math.abs(b[k-1]-b[k-6])==1) return;

22         }

23

24         if(k==a.length) {

25             sum++;

26             System.out.println(s);

27             return;

28         }

29         for(int i=0;i<a.length;i++){

30             String ss = s;

31             if(a[i]==-1) continue;

32             b[k] = a[i];

33             ss += a[i];

34             a[i] = -1;

35             f(a,b,k+1,ss);

36             a[i] = b[k];

37         }

38

39

40     }

第七届蓝桥杯javaB组真题解析-方格填数（第六题）的相关教程结束。