永安网页定制北京seo网站推广

一、题目

如【图1.jpg】, 有12张连在一起的12生肖的邮票。
现在你要从中剪下5张来，要求必须是连着的。
（仅仅连接一个角不算相连）
比如，【图2.jpg】，【图3.jpg】中，粉红色所示部分就是合格的剪取。

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

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

二、分析

要剪下五张邮票,且五张游标是相连的,观察合格的剪取可以发现,它满足以下特性:
1、两个方格在一行,则它们的值相差1
2、两个方格在一列,则它们的值相差4

那么就有了一条思路,先求这五个数的全排列,然后根据特性去搜索满足条件的排列。

三、代码

public class Main {static int a[] = new int[5];public static void main(String[] args) {int count = 0;// 取这五个数的全排列组合for (a[0] = 0; a[0] < 12; a[0]++) {for (a[1] = a[0] + 1; a[1] < 12; a[1]++) {for (a[2] = a[1] + 1; a[2] < 12; a[2]++) {for (a[3] = a[2] + 1; a[3] < 12; a[3]++) {for (a[4] = a[3] + 1; a[4] < 12; a[4]++) {if (judge()) {count++;}}}}}}System.out.println(count);}private static boolean judge() {boolean visit[] = new boolean[5];dfs(visit, 0);return visit[0] && visit[1] && visit[2] && visit[3] && visit[4];}// 通过dfs判断连通性private static void dfs(boolean[] visit, int i) {visit[i] = true;// 加一减一要在同一行、加四减四要在同一列for (int j = 0; j < visit.length; j++) {if (!visit[j] && (a[i] / 4 == a[j] / 4) && (a[i] == a[j] + 1 || a[i] == a[j] - 1)) {dfs(visit, j);}if (!visit[j] && (a[i] % 4 == a[j] % 4) && (a[i] == a[j] + 4 || a[i] == a[j] - 4)) {// 上下dfs(visit, j);}}}}

注:代码是从网上找的。

Travel hopefully is a better thing than to arrive,and true success is to labour.