第七届蓝桥杯 Java A—— 剪邮票

如下图，有 12 张连在一起的 12 生肖的邮票。
现在你要从中剪下 5 张来，要求必须是连着的
（仅仅连接一个角不算相连）

比如
粉红色所示部分就是合格的剪取。

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

这题不能单纯用 DFS 来做，如果用 DFS，是得不到类似 "T" 型格子的

正确做法是暴力枚举，从 12 个格子中枚举出 5 个格子，然后判断这 5 个格子是否连通，判断连通可以用 DFS

import java.util.*;

public class Main {

    static boolean[] book = new boolean[13];
    static int[] path = new int[5];
    static int[][] map = new int[3][4];
    static Set<String> set = new HashSet<String>();
    static int ans;
    
    public static void main(String[] args) {
        dfs(0);
        System.out.println(ans);
    }
    
    static void dfs(int idx) {
        if (idx == 5) {
            int[] tmp = Arrays.copyOf(path, 5);
            Arrays.sort(tmp);
            String str = tmp[0] + "" + tmp[1] + "" + tmp[2] + "" + tmp[3] + "" + tmp[4];
            if (!set.contains(str) && check()) {
                set.add(str);
                System.out.println(str);
                ans++;
            }
        } else {
            for (int i = 1; i <= 12; i++) {
                if (!book[i]) {
                    book[i] = true;
                    path[idx] = i;
                    dfs(idx + 1);
                    book[i] = false;
                }
            }
        }
    }

    static boolean check() {
        map = new int[4][5];
        for (int i = 1; i <= 3; i++)
            for (int j = 1; j <= 4; j++)
                for (int t = 0; t < 5; t++)
                    if ((i - 1) * 4 + j == path[t])
                        map[i][j] = 1;
        
        // dfs check connected
        int cnt = 0;
        for (int i = 1; i <= 3; i++)
            for (int j = 1; j <= 4; j++)
                if (map[i][j] == 1) {
                    dfs_connect(i, j);
                    cnt++;
                }
        return cnt == 1;
    }

    static void dfs_connect(int i, int j) {
        map[i][j] = 0;
        if (i + 1 <= 3 && map[i + 1][j] == 1) dfs_connect(i + 1, j);
        if (j + 1 <= 4 && map[i][j + 1] == 1) dfs_connect(i, j + 1);
        if (i - 1 >= 1 && map[i - 1][j] == 1) dfs_connect(i - 1, j);
        if (j - 1 >= 1 && map[i][j - 1] == 1) dfs_connect(i, j - 1);
    }
}