第七届蓝桥杯Java A——搭积木

小明最近喜欢搭数字积木,

一共有10块积木,每个积木上有一个数字,0~9。

搭积木规则:

每个积木放到其它两个积木的上面,并且一定比下面的两个积木数字小。

最后搭成4层的金字塔形,必须用完所有的积木。

下面是两种合格的搭法:

0

1 2

3 4 5

6 7 8 9

0

3 1

7 5 2

9 8 6 4

请你计算这样的搭法一共有多少种?

public class Main {
    static int ans;
    static int[] book = new int[11];
    static int[][] map = new int[5][5];
    public static void main(String[] args) {
        dfs(4, 0); // Fourth Layer 
        System.out.println(ans);
    }
    static void dfs(int layer, int idx) {
        if (layer == 0) {
            ans++;
        } else {
            for (int i = 0; i <= 9; i++) {
                if (layer == 4) {
                    if (book[i] == 0) {
                        book[i] = 1;
                        map[layer][idx] = i;
                        dfs(idx + 1 == layer ? layer - 1 : layer, (idx + 1) % layer);
                        book[i] = 0;
                    }
                } else {
                    if (check(layer, idx, i)) {
                        book[i] = 1;
                        map[layer][idx] = i;
                        dfs(idx + 1 == layer ? layer - 1 : layer, (idx + 1) % layer);
                        book[i] = 0;
                    }
                }
            }
        }
    }
    private static boolean check(int layer, int idx, int i) {
        return book[i] == 0 && i < map[layer + 1][idx] && i < map[layer + 1][idx + 1];
    }
}

原文 

https://www.wmathor.com/index.php/archives/1261/

本站部分文章源于互联网,本着传播知识、有益学习和研究的目的进行的转载,为网友免费提供。如有著作权人或出版方提出异议,本站将立即删除。如果您对文章转载有任何疑问请告之我们,以便我们及时纠正。

PS:推荐一个微信公众号: askHarries 或者qq群:474807195,里面会分享一些资深架构师录制的视频录像:有Spring,MyBatis,Netty源码分析,高并发、高性能、分布式、微服务架构的原理,JVM性能优化这些成为架构师必备的知识体系。还能领取免费的学习资源,目前受益良多

转载请注明原文出处:Harries Blog™ » 第七届蓝桥杯Java A——搭积木

赞 (0)
分享到:更多 ()

评论 0

  • 昵称 (必填)
  • 邮箱 (必填)
  • 网址