蓝桥杯 方格分割

Posted on | In |

标题：方格分割

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

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

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

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

image
vis[x][y] 并不是指这个方块是否访问
而是指坐标点 线与线的交点是否被访问过（因为一个个点连起来才成了线 分割线）
所以要vis[n+1][n+1]

从中心点坐标（3,3）向两边dfs一个中心对称的路径，这里搜的是方格的边线而不是方格，因为dfs只能搜索连续的。搜索结束的标志是搜到大方块的边界即：x = 0||x = 6||y = 0||y = 6，因为如果向上下左右的路径形状是一样的的话，就重复了所以搜索结果再除以4即是最终答案。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
#include<bits/stdc++.h>
#include<iostream>
using namespace std;
const int n=6;
bool vis[10][10];
int dir[4][2]={{-1,0},{1,0},{0,1},{0,-1}};
int cnt=0;
void dfs(int x,int y) {
	if(x==0||x==n||y==0||y==n) {
		cnt++;
		return;
	}

	for(int i=0;i<4;i++){
		int newx=x+dir[i][0];
		int newy=y+dir[i][1];
		if(!vis[newx][newy]&&newx>=0&&newx<=6&&newy>=0&&newy<=6){
			vis[newx][newy]=true;
			vis[n-newx][n-newy]=true;
		dfs(newx,newy);
		vis[newx][newy]=false;
			vis[n-newx][n-newy]=false;
			
		}
			
	}
}
int main()
{
	vis[3][3]=true;
	dfs(3,3);
	cout<<cnt/4<<endl;
}