有12张连在一起的12生肖的邮票。
现在你要从中剪下5张来,要求必须是连着的。
(仅仅连接一个角不算相连)
请你计算,一共有多少种不同的剪取方法。
import java.util.HashSet; public class Main{ //存储剪那些邮票的位置 static int[] map = new int[5]; //判断当前位置的邮票是否已经被剪掉 static int[] visit = new int[13]; //存储剪邮票的方案数 static HashSet<HashSet<Integer>> set = new HashSet<HashSet<Integer>>(); public static void main(String[] args) { dfs(0); System.out.println(set.size()); } //全排列 public static void dfs(int n) { if(n == 5) { //局部变量,存储本次剪那些邮票 HashSet<Integer> s = new HashSet<>(); for(int i = 0;i < 5;i++) { s.add(map[i]); } //去重 set.add(s); return; } for(int i = 1;i < 13;i++) { //当前位置没有被剪掉 并判断当前位置能不能被剪 if(visit[i] == 0 && check(n,i)) { //当前位置被剪 visit[i] = 1; //第n个邮票剪的位置 map[n] = i; //判断下一个 dfs(n + 1); //回溯 visit[i] = 0; } } } public static boolean check(int n,int i) { if(n == 0) { return true; } for(int k = 0;k < n;k++) { //判断这两个邮票是否相邻 if(adjust(map[k],i)) { return true; } } return false; } public static boolean adjust(int m,int n) { //判断上下是否相邻 Math.abs(m - n); //判断左右是否相邻,且小的值不能是边界 Math.abs(m - n) == 1 && Math.min(m,n) % 4 != 0 if(Math.abs(m - n) == 4 || (Math.abs(m - n) == 1 && Math.min(m, n) % 4 != 0)) { return true; } return false; } }