JAVA藍橋杯剪郵票_java算法 第七屆 藍橋杯B組（題+答案） 7.剪郵票

7.剪郵票  (結果填空)

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

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

(僅僅連接配接一個角不算相連)

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

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

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

注意：你送出的應該是一個整數，不要填寫任何多餘的内容或說明性文字。

思路： 感覺還是先排列，從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