Java│蓝桥杯省赛真题方格分割问题

题目描述

题目：方格分割

http://oj.ecustacm.cn/problem.php?id=1320

6x6的方格，沿着格子的边线剪开成两部分。要求这两部分的形状完全相同。
试计算：一共有多少种不同的分割方法。注意：旋转对称的属于同一种分割法。

题解

又是暴搜。第1题DFS，第2题BFS，第3题BFS，这题又回到DFS。下一题估计是BFS？
倪文迪的话：“这道题可能上来会想到搜格子，但搜格子意味着更高的复杂度以及判连通的需要，本题似乎搜索要切开的边更优。由题意，这一条切割线必定经过图的中心点，那么我们一旦确定了半条到达边界的分割线，就能根据这半条对称画出另外半条。而由于结果中心对称性，搜索出来的个数应该除以4得出最终结论。在搜索过程中需要注意的是，我们搜索出的半条分割线不能同时经过关于中心对称的两个点，所以在标记时，需要将对称的点也标上。”

中心点是(3,3)，从（3,3）出发，向右、向左、向上、向下，四个方向DFS即可。

代码实现

public class Main {
    private static int ans = 0;
    private static int[][] dir = {{1,0},{-1,0},{0,1},{0,-1}};
    private static boolean[][] visit = new boolean[7][7];
 
    public static void main(String[] args) {
        visit[3][3] = true;
        dfs(3,3);
        System.out.println(ans / 4);
    }
 
    private static void dfs(int x,int y){
        if (x == 0 || y == 0 || x == 6 || y == 6){
            ans ++;
            return;
        }
        visit[x][y] = true;
        visit[6 - x][6 - y] = true;
        for (int i = 0; i < 4; i++) {
            int nx = x + dir[i][0];
            int ny = y + dir[i][1];
            if (nx < 0 || nx > 6 || ny < 0 || ny > 6)
                continue;
            if (!visit[nx][ny])
                dfs(nx,ny);
        }
 
        visit[x][y] = false;
        visit[6 - x][6 - y] = false;
    }
}