MENU

第八届蓝桥杯Java B——纸牌三角形

March 17, 2019 • Read: 250 • 算法

A,2,3,4,5,6,7,8,9 共9张纸牌排成一个正三角形(A按1计算)。要求每个边的和相等。

下图就是一种排法

这样的排法可能会有很多。

如果考虑旋转、镜像后相同的算同一种,一共有多少种不同的排法呢?

import java.util.HashSet;
import java.util.Set;

public class Main {
    static boolean[] book = new boolean[9];
    static int[] arr = new int[9];
    static int ans;
    static Set<String> set = new HashSet<String>();

    public static void main(String[] args) {
        dfs(0);
        System.out.println(ans);
    }

    // 金字塔顶是arr[0],剩下的顺序按照顺时针排下来
    static void dfs(int idx) {
        if (idx == 7 && check_7()) // 剪枝
            return;
        else if (idx == 9) {
            if (check_9()) {
                StringBuilder a = new StringBuilder("").append(arr[0]).append(arr[1]).append(arr[2]).append(arr[3]);
                StringBuilder b = new StringBuilder("").append(arr[3]).append(arr[4]).append(arr[5]).append(arr[6]);
                StringBuilder c = new StringBuilder("").append(arr[6]).append(arr[7]).append(arr[8]).append(arr[0]);
                if (!set.contains(a + "" + b + c)) {
                    set.add(a + "" + b + c);
                    set.add(b + "" + c + a);
                    set.add(c + "" + a + b);
                    a.reverse();b.reverse();c.reverse();
                    set.add(c + "" + b + a);
                    set.add(a + "" + c + b);
                    set.add(b + "" + a + c);
                    ans++;
                }
            }
            return;
        }
        for (int i = 1; i <= 9; i++) {
            if (!book[i - 1]) {
                book[i - 1] = true;
                arr[idx] = i;
                dfs(idx + 1);
                book[i - 1] = false;
            }
        }
    }

    static boolean check_9() {
        return arr[0] + arr[1] + arr[2] + arr[3] == 
               arr[3] + arr[4] + arr[5] + arr[6] && 
               arr[3] + arr[4] + arr[5] + arr[6] ==
               arr[6] + arr[7] + arr[8] + arr[0];
    }

    static boolean check_7() {
        return arr[0] + arr[1] + arr[2] != arr[4] + arr[5] + arr[6];
    }
}
Archives Tip
QR Code for this page
Tipping QR Code