2017年蓝桥杯A组 方格分割（dfs）

标题：方格分割

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

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

如图4-1,4-2,4-3：就是可行的分割法。

试计算：

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

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

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

题目分析：可以抽象成深度优先搜索问题，不考虑格子，考虑线的交点，并以中间点开始向上下左右是个方向分别遍历，遍历的同时遍历互相对称的另外一边的点。到达边界之后即ans++；不过最后的答案记得要除以4，因为题目说了旋转对称的属于同一种分法。

    答案是509.

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;

int dx[4] = {0,0,1,-1};
int dy[4] = {1,-1,0,0};
bool vis[10][10];
int N = 6;
int counts = 0;
void dfs(int x,int y)
{
//	vis[x][y] = 1;
	if(x == N || y == N || x == 0 || y == 0)
	{
			counts++; 
			return;
	}
	
	for(int i = 0; i < 4; i++)
	{
		int tx = dx[i] + x;
		int ty = dy[i] + y;
		
		if(tx <= N && tx >= 0 && ty <= N && ty >= 0 && vis[tx][ty] == 0)
		{
			vis[tx][ty] = 1;
			vis[N-tx][N-ty] =1;
			
			dfs(tx,ty);
			
			vis[tx][ty] = 0;
			vis[N-tx][N-ty] =0;
		}
	}
}
int main()
{
	memset(vis,0,sizeof(vis));
	vis[3][3] = 1;
	dfs(3,3);
	cout<<counts/4<<endl;
	return 0;
}