2017年蓝桥杯A组 方格分割(dfs)

时间:2022-09-09 23:21:38

标题:方格分割

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