剪郵票java實作

題目描述

如【圖1.jpg】, 有12張連在一起的12生肖的郵票。

現在你要從中剪下5張來，要求必須是連着的。

（僅僅連接配接一個角不算相連）

比如，【圖2.jpg】，【圖3.jpg】中，粉紅色所示部分就是合格的剪取。

請你計算，一共有多少種不同的剪取方法。

請填寫表示方案數目的整數。

題目思路：

1.首先得到所有從12個數中找5個數的排列

2. 然後對數組進行指派(模拟剪裁的動作)

3. 對指派完後的數組進行檢檢視是否滿足連通性

import java.util.ArrayList;
import java.util.List;

public class Main {
    private static int N=0;
    public static void main(String[] args) {
        int[] arr=new int[12];
        //初始化數組
        for (int i=0;i<12;i++){
            arr[i]=i+1;
        }
        List<Integer> path = new ArrayList<>();
        List<List<Integer>> res=new ArrayList<>();
        //全排列
        dfs(res,path,1);
        for (List<Integer> elem:res){
            System.out.println(elem);
        }
        System.out.println(N);
    }

    private static void dfs(List<List<Integer>> res, List<Integer> path, int begin) {
        //遞歸終止條件
        if (path.size()==5){
            //對目前path數組對應的情況進行檢查
            if (check(path)){
                //如果符合條件
                res.add(new ArrayList<>(path));
                N++;
            }
            return;
        }
        for (int i=begin;i<=12;i++){
            path.add(i);
            //遞歸
            dfs(res, path, i+1);
            //回溯
            path.remove(path.size()-1);
        }
    }

    private static boolean check(List<Integer> path) {
        int[][] arr=new int[3][4];
        //根據排列結果初始化數組
        for (Integer elem:path){
            if (elem<=4){
                arr[0][elem-1]=1;
            }else if (elem>4&&elem<=8){
                arr[1][elem-5]=1;
            }else {
                arr[2][elem-9]=1;
            }
        }
        //判斷此時的二維數組是否是符合題目的要求也就是是否連着
        //将問題轉換成二維數組的連通性問題
        int count=0;
        for (int i=0;i<3;i++){
            for (int j=0;j<4;j++){
                if (arr[i][j]==1){
                    function(arr,i,j);
                    count++;
                }
            }
        }
        return count==1;
    }

    private static void function(int[][] arr, int i, int j) {//arr是引用傳遞
        arr[i][j]=0;//将目前位置改為0，防止死循環
        if (i-1>=0&&arr[i-1][j]==1) function(arr,i-1,j);
        if (i+1<=2&&arr[i+1][j]==1) function(arr,i+1,j);
        if (j-1>=0&&arr[i][j-1]==1) function(arr,i,j-1);
        if (j+1<=3&&arr[i][j+1]==1) function(arr,i,j+1);

    }
}
/**
 * 首先将所有的得到從12個數中找5個數的全排列
 * 然後對每種排列進行檢查
 */