（算法）DFS深度优先搜索—2016年蓝桥杯省赛java剪邮票

（算法）DFS深度优先搜索—2016年蓝桥杯省赛java剪邮票

2016年蓝桥杯剪邮票原题：

如【图1.jpg】, 有12张连在一起的12生肖的邮票。
现在你要从中剪下5张来，要求必须是连着的。
（仅仅连接一个角不算相连）
比如，【图2.jpg】，【图3.jpg】中，粉红色所示部分就是合格的剪取。

请你计算，一共有多少种不同的剪取方法。

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

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

题目的整个思路应该是很明显的，从12个数中选5个（无重组合问题），判断满足题意的组合个数，即是本题的答案。组合的递归算法在以前的文章中详细写过，如有不清楚的地方，请参考组合的递归算法Java实现过程

难点在于如何判断组合是否符合题意

一开始，我想着把所有满足题意的情况的特有数学特征找到，以为为条件进行判断。如公共边数特征等等，虽然最后也算出结果，但是是在知道答案的前提下，一步步加判断，逆向把答案凑出来的，如果不知道答案，相信大多数人都不能保证自己考虑全了所有可能。

以这个思路想了很久，都没找到好的解法。

网上各种DFS解法很少解析，每人一个思路，我比较笨，递归到头疼

但又从另一个角度考虑，回归最原始的算法，这完全是个通过DFS算法判定是否是连通图的实例模型。

大体思路如下：

1、inArr为12个邮票的编号，这里参考了网上的各位大神的思路，将12张邮票重写编号：

之所以这样编号，是因为容易判断两个元素是否相邻。任意两个元素如果相差1或者相差5就是相邻的
2、如果满足题意，如下图

取到的outArr为[3,8,9,12,13]，执行dfs()方法： 以3为第一个节点进行dfs遍历（深度优先搜索），则为[3,8,9,13,12]，对应visit为[true,true,true,true,true]，说明以一个节点可以全部遍历，则满足题意

如果不满足题意，如下图：

此时取到的outArr为[2,4,7,9,14]，dfs遍历结果为[2,7]，对应visit为[true,false,true,false,false]，所以不满足题意

代码及注释如下：

public class test7_2 {
    /*12张邮票编号放入数组*/
    private static int[] inArr = {1,2,3,4,6,7,8,9,11,12,13,14};
    /*存放剪下邮票编号的数组*/
    private static int[] outArr = new int[5];
    /*表示outArr的索引*/
    private static int index;

    /*满足题意的outArr组数*/
    private static int cnt = 0;

    /*判断是否连通时，用于记录访问过的索引，即如果visit[1]为true，则outArr[1]已经被访问*/
    private static boolean[] visit = new boolean[5];


    /** * @param arr * @param n * @return 返回在arr中与n相邻的所有元素索引的集合 * 例如：arr为[1,2,6,7,8],n为7，在arr中与7相邻的有[2,8]，则返回的List中为[2,8]的索引值，即 {1,4} */
    private static List<Integer> getCon(int[]arr , int n){
        List<Integer> out = new ArrayList<Integer>();
        for(int i=0;i<arr.length;i++){
            if(Math.abs(n - arr[i])==1 || Math.abs(n - arr[i])==5){//相差1或4为相邻
                out.add(i); 
            }
        }
        return out;
    }

    /** * 典型的DFS算法 * DFS遍历arr[]，并操作处理visit数组，把遍历过的数的索引对于的visit元素置为true * @param arr 要遍历的数组 * @param index 待访问的节点索引 */
    private static void dfs(int[] arr,int index){
        if(visit[index]) return ; //如果arr[index]已经访问过了，直接返回访问下一个
        visit[index] = true; //arr[index]没有被访问，把visit[index]置为true，表示现在访问它
        for(Integer i:getCon(arr,arr[index])){//遍历与arr[index]索引相邻的节点
            dfs(arr,i);
        }
    }

    /** * 12个数选5个，m<=0为递归头，此时outArr已经取到了一组结果，再用dfs()方法验证是否满足题意 * @param inArr * @param n * @param m */
    private static void Choice(int[] inArr , int n, int m){
        if(m<=0){
            dfs(outArr,0); //dfs遍历一次outArr 
            if(visit[0] && visit[1] && visit[2] && visit[3] && visit[4]) //如果visit中全为true，即outArr可以以一个节点遍历完
                cnt++;
            visit = new boolean[5];//恢复visit全为false,进行一下个outArr的验证
        }else{
            for(int i = n; i<= inArr.length-m;i++){
                outArr[index++] = inArr[i];
                Choice(inArr,i+1,m-1);
                index--;
            }
        }
    }




    public static void main(String[] args) {
        Choice(inArr,0,5);
        System.out.println(cnt);
    }
}