DFS之方格分割java

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
	}
}