转载

第八届蓝桥杯Java A——方格分割

6x6的方格，沿着格子的边线剪开成两部分。

要求这两部分的形状完全相同。

如图：p1.png, p2.png, p3.png 就是可行的分割法。

试计算：

包括这3种分法在内，一共有多少种不同的分割方法。

注意：旋转对称的属于同一种分割法。

public class Main {

    static boolean[][] map = new boolean[7][7];
    static int[][] dr = { { 0, 1 }, { 0, -1 }, { -1, 0 }, { 1, 0 } };
    static int ans;

    public static void main(String[] args) {
        map[3][3] = true;
        dfs(3, 3);
        System.out.println(ans >> 2);
    }

    static void dfs(int x, int y) {
        if (x == 0 || x == 6 || y == 0 || y == 6)
            ans++;
        else {
            for (int i = 0; i < 4; i++) {
                int nx = x + dr[i][0];
                int ny = y + dr[i][1];
                if (check(nx, ny)) {
                    map[nx][ny] = true;
                    map[6 - nx][6 - ny] = true;
                    dfs(nx, ny);
                    map[nx][ny] = false;
                    map[6 - nx][6 - ny] = false;
                }
            }
        }
    }

    static boolean check(int nx, int ny) {
        return nx >= 0 && nx <= 6 && ny >= 0 && ny <= 6 && !map[nx][ny];
    }
}

原文 https://www.wmathor.com/index.php/archives/1281/

正文到此结束