DFS之方格分割java

问题描述
6x6的方格，沿着格子的边线剪开成两部分。
要求这两部分的形状完全相同。
试计算：
一共有多少种不同的分割方法。
注意：旋转对称的属于同一种分割法。
请提交该整数，不要填写任何多余的内容或说明文字。

watermark,type_d3F5LXplbmhlaQ,shadow_50,text_Q1NETiBAcXFfNTIzNjAwNjk=,size_20,color_FFFFFF,t_70,g_se,x_16

具体思路
既然要求剪下来的两部分完全相同，那么剪的路线一定通过图的中心点，并且分割线一定关于中心点对称。因此可以以图中的交点为元素，将66的方格转换成77的网格，从中心点开始对称的向边界dfs深度遍历，即从中心点开始向上下左右标记的同时，对称的位置也要标记。例如（3,3）->(4,3)的同时，(3,3) -> (2,3)也要标记。当遍历到网格的边界即剪完成，然后进行回溯。

代码

public class _方格分割 {

static int[][] map = new int[7][7];//网格线
static int[][] v = new int[7][7];//标记当前点是否访问过，即当前位置是否已经剪过
static int ans = 0;//最终答案
static int[][] step = { { 1, 0 }, { 0, 1 }, { -1, 0 }, { 0, -1 } };//上下左右坐标变换

static void dfs(int x, int y) {
    // 首先判断是否到达边界
    if (x == 0 || y == 0 || x == 6 || y == 6) {
        ans++;
        return;
    }
    // 对称标记已经剪过该位置
    v[x][y] = 1;
    v[6 - x][6 - y] = 1;
    // 依次上下左右剪
    for (int i = 0; i < 4; i++) {
        int newx = x + step[i][0];
        int newy = y + step[i][1];
        // 判断当前位置是否剪过并且没有越界
        if (v[newx][newy] == 0 && newx >= 0 && newx <= 6 && newy >= 0 && newy <= 6) {
            dfs(newx, newy);// 向下一步剪
        }
    }
    // 剪完过后记得回溯
    v[x][y] = 0;
    v[6 - x][6 - y] = 0;
}

public static void main(String[] args) {
    dfs(3, 3);// 从(3,3)开始中心对称位置剪
    System.out.println(ans / 4);// 因为中心对称剪的话，每条路线可绕中心点旋转一周，因此一条路线重复了4次，所以要将最后结果/4
}

}