如【图1.jpg】, 有12张连在一起的12生肖的邮票。
现在你要从中剪下5张来,要求必须是连着的。
(仅仅连接一个角不算相连)
比如,【图2.jpg】,【图3.jpg】中,粉红色所示部分就是合格的剪取。
请你计算,一共有多少种不同的剪取方法。
请填写表示方案数目的整数。
注意:你提交的应该是一个整数,不要填写任何多余的内容或说明性文字。
解题思路一:
枚举<a, b, c, d, e>五元组合,保证a<b<c<d<e。判断abcde是否连在一起。
判断连在一起的方法:
集合S = {第1张}, 集合T = {其余4张}for i = 0 … 3:
for j in T:
if 第j张与S中某张相连 then S = S + {第j张}, T = T – {第j张}
例:选择的是3,5,6,7,10 必须保证顺序,再判断是否相连
注意点:1.由于是组合问题,选出的五个数没有顺序之分,在进行组合时由于是递增的选择,所以不需要uesd来判断是否访问过
也不需要判重。
2.在进行节点是否相邻的判断时,需要使用set集合边判断边插入,在java中,不能使用HashSet,要用ConcurrentSkipListSet
java代码如下:
package 剪邮票; import java.util.Set; import java.util.concurrent.ConcurrentSkipListSet; public class Main { /** * 思路1:枚举<a, b, c, d, e>五元组合,保证a<b<c<d<e。判断abcde是否连在一起。 集合S = {第1张}, 集合T = {其余4张} for i = 0 … 3: for j in T: if 第j张与S中某张相连 then S = S + {第j张}, T = T – {第j张} * @param args */ static int a[]=new int[5]; static int ants=0; public static void main(String[] args) { // TODO Auto-generated method stub dfs(0,0); System.out.println(ants); } /** * adj方法:判断x和y数字是否相邻 * @param x * @param y * @return */ public static boolean adj(int x,int y){ if(x>y){ int t=x; x=y; y=t; } if(y-x==4||(y-x==1&&x%4!=0)) return true; return false; } /** * 判断枚举的五个数是否都满足连在一起 * @return */ public static boolean check(){ Set<Integer>set=new ConcurrentSkipListSet<Integer>(); //使用ConcurrentSkipListSet,是因为在foreach遍历时,set集合会被修改,不能使用HashSet set.add(a[0]); for(int i=0;i<4;i++){ for(int k=1;k<5;k++){ for(int x:set){ if(adj(a[k],x)) set.add(a[k]); } } } return set.size()==5; } public static void dfs(int x,int pre){ if(x==5){ if(check()) ants++; return ; } for(int i=pre+1;i<=12;i++){ a[x]=i; dfs(x+1,i); } } }
结果为116
方法二:
枚举第1张,第2张……第5张邮票,并且保证第i张与之前的i-1张中至少一张相连,最后需要判重。
例:选择第一张为3,则第二张就要从2,7,4中选。选择3,7,6,5,10 和3,7,6,10,5是一样的,所以需要判重。
判重应用的技巧:使用超级集合Set的嵌套,将枚举好的一个组合a[0-5]转换成set集合,如果重复则加入不到超级集合中,最后超级集合的大小即为所求值。
代码如下:
package 剪邮票2; import java.util.Arrays; import java.util.HashSet; import java.util.Set; public class Main { static int a[]=new int[5]; static int ants=0; static Set<HashSet<Integer>>set=new HashSet<HashSet<Integer>>(); static boolean used[]=new boolean[13]; /** * 超级集合Set用于判重 * @param args */ public static void main(String[] args) { // TODO Auto-generated method stub Arrays.fill(used, false); dfs(0); System.out.println(set.size()); } //判断x,y是否相邻 public static boolean adj(int x,int y){ if(x>y){ int t=x; x=y; y=t; } if(y-x==4||(y-x==1&&x%4!=0)) return true; return false; } //判断a[0]-a[x-1]中是否有元素与i相邻 public static boolean check(int x,int i){ if(x==0) return true; for(int k=0;k<x;k++){ if(adj(a[k],i)) return true; } return false; } public static void dfs(int x){ if(x==5){ HashSet<Integer>s=new HashSet<Integer>(); for(int k=0;k<5;k++){ s.add(a[k]); } //将当前数组装换成集合加入到超级集合中,最后超级集合的大小就是不重复的满足条件的结果个数 set.add(s); return ; } for(int i=1;i<=12;i++){ if(!used[i]&&check(x,i)){//数字i没被用过并且i还有a[0]-a[x-1]中某个数相邻 a[x]=i; used[i]=true; dfs(x+1); used[i]=false; } } } }
两方法的区别:方法一是按从小到大的顺序枚举邮票,判断是否相连
方法二是从相连的邮票中选择,判断是否重复