JAVA蓝桥杯剪邮票_java算法第七届蓝桥杯B组（题+答案） 7.剪邮票

逃离我推掉我的手 2022-10-23 03:00 185阅读 0赞

7.剪邮票  (结果填空)

如【图1.jpg】, 有12张连在一起的12生肖的邮票。

现在你要从中剪下5张来，要求必须是连着的。

(仅仅连接一个角不算相连)

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

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

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

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

![f4e722d0513046d090830de6fc4ef6ee.png][]

思路： 感觉还是先排列，从12个邮票中选5个出来，

然后对每个邮票搜索，同一行，同一列，则表示连接到，如果连接到就定义

该块邮票被访问过，最后判断5个邮票是否都被访问过，是就说明是连通的，

但是这个不是全排列，应该是从12个选5个出来

从12个选5个。判断5个是否相连，符合一个visit设为true，五个true，count++

(这个题没弄懂，参考网上的)

1 public class\_7剪邮票 \{2 static int a\[\] = new int\[5\];3 public static voidmain(String\[\] args) \{4 int count = 0;5 for (a\[0\] = 0; a\[0\] < 12; a\[0\]++) \{6 for (a\[1\] = a\[0\] + 1; a\[1\] < 12; a\[1\]++) \{7 for (a\[2\] = a\[1\] +1 ; a\[2\] < 12; a\[2\]++) \{8 for (a\[3\] = a\[2\]+1; a\[3\] < 12; a\[3\]++) \{9 for (a\[4\] = a\[3\]+1; a\[4\] < 12; a\[4\]++) \{10 if(judge()) \{11 count++;12 \}13 \}14 \}15 \}16 \}17 \}18 System.out.println(count);19 \}20 private static booleanjudge() \{21 boolean visit\[\] = new boolean\[5\];22 dfs(visit,0);23 return visit\[0\]&&visit\[1\]&&visit\[2\]&&visit\[3\]&&visit\[4\];24 \}25

26 private static void dfs(boolean\[\] visit, inti) \{27 visit\[i\] = true;28 for (int j = 0; j < visit.length; j++) \{29 if (!visit\[j\]&&(a\[i\]/4==a\[j\]/4)&&(a\[i\]==a\[j\]+1||a\[i\]==a\[j\]-1)) \{30 dfs(visit, j);31 \}32 if (!visit\[j\]&&(a\[i\]==a\[j\]+4||a\[i\]==a\[j\]-4)) \{33 dfs(visit, j);34 \}35 \}36 \}37 \}

运行结果：116

原文：http://www.cnblogs.com/zhangxue521/p/6538570.html

[f4e722d0513046d090830de6fc4ef6ee.png]: /images/20221022/c7cdc502825e468bb9de6c02314e2acf.png