剪邮票

如图, 有12张连在一起的12生肖的邮票。

现在你要从中剪下5张来，要求必须是连着的。
（仅仅连接一个角不算相连）
比如这两张图中，粉红色所示部分就是合格的剪取。

请你计算，一共有多少种不同的剪取方法。
请填写表示方案数目的整数。
注意：你提交的应该是一个整数，不要填写任何多余的内容或说明性文字。

从小到大选取数字的组合（如果不从小到大，从邮票2开始剪和从邮票12开始剪会出现图2相同的情况），再在这些组合里判断相联通的情况。
判断联通：设置一个布尔型的数组来表示是否联通，这里判断条件设置得很巧妙，因为在第一步组合邮票的时候是从0开始的，所以如果两张邮票除以4结果相同而且相差1就说明横排相连，如果相差4就说明纵列相连
最后如果布尔数组内的元素都被赋值为true则说明联通

下面附上代码：

public class ResultFilling7 {
    static int stamps[] = new int[5];

    public static void main(String[] args) {
        int count = 0;
        // 从小到大的顺序剪邮票
        for (stamps[0] = 0; stamps[0] < 12; stamps[0]++) {
            for (stamps[1] = stamps[0] + 1; stamps[1] < 12; stamps[1]++) {
                for (stamps[2] = stamps[1] + 1; stamps[2] < 12; stamps[2]++) {
                    for (stamps[3] = stamps[2] + 1; stamps[3] < 12; stamps[3]++) {
                        for (stamps[4] = stamps[3] + 1; stamps[4] < 12; stamps[4]++) {
                            if (judge()) {
                                count++;
                            }
                        }
                    }
                }
            }
        }
        System.out.println(count); // 最终运行结果：116
    }

    // 判断是否联通
    private static boolean judge() {
        boolean visit[] = new boolean[5];
        dfs(visit, 0);
        return visit[0] && visit[1] && visit[2] && visit[3] && visit[4];
    }

    private static void dfs(boolean[] visit, int i) {
        visit[i] = true;
        for (int j = 0; j < visit.length; j++) {
            // 判断是否横排相连
            if (!visit[j] && (stamps[i] / 4 == stamps[j] / 4) && (stamps[i] == stamps[j] + 1 || stamps[i] == stamps[j] - 1)) {
                dfs(visit, j);
            }
            // 判断是否纵列相连
            if (!visit[j] && (stamps[i] == stamps[j] + 4 || stamps[i] == stamps[j] - 4)) {
                dfs(visit, j);
            }
        }
    }
}

这里参考了obession的解答，并对其代码详细地解释了一下
原文链接=》蓝桥杯-第七届省赛javaA组-剪邮票
下面是我最初的错误的做法，我是这样想的：

把所有相连的情况用一种数据结构存起来，也就是代码中的HashMap映射，再用一个布尔数组来表示邮票是否被剪，如果能够连续剪5张邮票，则可能的情况数加一，想法是可以的，但是稍加分析就可以看到存在很多问题。
main方法里面只写了从1开始剪的情况，那么从其他张邮票开始剪的情况就没有杯考虑到了，另外，如果从各个邮票开始剪，有怎么考虑重叠的情况呢（上面说的剪法不同，剪出的五张连邮相同）。
其实这种想法是来自于上一题，上一题就是用这种想法做出来的，上一题链接=》第七届蓝桥杯个人赛省赛（Java B组）第六题，后面我也没有想该怎么改进了，有想法的朋友欢迎留言。

下面是错误的代码：

public class ResultFilling7 {
    public static int counter = 0;
    public static boolean[] isCut = new boolean[13];
    public static Map<Integer, int[]> map = new HashMap<Integer, int[]>();

    public static void cut(int num, int stamps) {
        if (num == 6) {
            counter++;
            return;
        }
        int[] a = map.get(stamps);
        for (int i = 0; i < a.length; i++) {
            if (!isCut[a[i]]) {
                isCut[a[i]] = true;
                cut(num + 1, a[i]);
                isCut[a[i]] = false;
            }
        }
    }

    public static void main(String[] args) {
        map.put(1, new int[] { 2, 5 });
        map.put(2, new int[] { 1, 3, 6 });
        map.put(3, new int[] { 2, 4, 7 });
        map.put(4, new int[] { 3, 8 });
        map.put(5, new int[] { 1, 6, 9 });
        map.put(6, new int[] { 2, 5, 7, 10 });
        map.put(7, new int[] { 3, 6, 8, 11 });
        map.put(8, new int[] { 4, 7, 12 });
        map.put(9, new int[] { 5, 10 });
        map.put(10, new int[] { 6, 9, 11 });
        map.put(11, new int[] { 7, 10, 12 });
        map.put(12, new int[] { 8, 11 });
        for (int i = 0; i < isCut.length; i++) {
            isCut[i] = false;
        }
        isCut[1] = true;
        cut(1, 1);
        System.out.println(counter);
    }
}

秒客网

第七届蓝桥杯个人赛省赛（Java B组）第七题

剪邮票

相关文章