【回溯】B040_LQ_方格分割（双向dfs）

一、Problem

6x6 的方格，沿着格子的边线剪开成两部分。要求这两部分的形状完全相同。

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

试计算：包括这3种分法在内，一共有多少种不同的分割方法。注意：旋转对称的属于同一种分割法。

请提交该整数，不要填写任何多余的内容或说明文字。

509

二、Solution

方法一：双向 dfs

错误思路：从点 (0, 0) 开始 dfs 进行全局搜索，但是 dfs 是一笔画的，所以求不出正解…

别人的思路：从方格的中心点 (3, 3) 开始双向 dfs。

• Q1：为什么这样做是对的呢？
  A1：因为，我每次 Fill 的时候，都去标记某一点的点以及它的中心对称点为访问过。
• Q2：最后的答案为什么要除以 4 ?
  A2：例如从点（3,3）点出发一直向东西南北四个方向之一不断扩散，那样分割出来的图形其实是算一种的。

import java.util.*;
import java.math.*;
import java.io.*;
public class Main{
	static int N = 6;
	static boolean[][] vis;
	static int res;
	final static int[][] dir = { {1,0},{0,-1},{0,1},{-1,0} };
	static void dfs(int x, int y) {
		if (x == 0 || x == N || y == 0 || y == N) {
			res++;
			return;
		}
		for (int k = 0; k < 4; k++) {
			int tx = x + dir[k][0];
			int ty = y + dir[k][1];
			if (x < 0 || x > N || y < 0 || y > N || vis[tx][ty])
				continue;
			vis[tx][ty] = true;
			vis[N-tx][N-ty] = true;
			dfs(tx, ty);
			vis[tx][ty] = false;
			vis[N-tx][N-ty] = false;
		}
	}
    public static void main(String[] args) throws IOException {  
        Scanner sc = new Scanner(new BufferedInputStream(System.in));
		vis = new boolean[N+1][N+1];
		int h = N >>> 1;
		vis[h][h] = true;;
		dfs(h, h);
		System.out.println(res/4);
    }
}

复杂度分析

• 时间复杂度：$O(2^n)$O(2n)，
• 空间复杂度：$O(n)$O(n)，