欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

蓝桥杯 方格分割

程序员文章站 2024-02-11 09:22:40
...

题目
6x6的方格,沿着格子的边线剪开成两部分。
要求这两部分的形状完全相同。
蓝桥杯 方格分割
蓝桥杯 方格分割
蓝桥杯 方格分割
试计算:
包括这3种分法在内,一共有多少种不同的分割方法。
注意:旋转对称的属于同一种分割法。

思路:

答案:509

刚开始把这道题目想的好复杂,后来看了大佬的代码,才发现原来这么简单。分割6x6的方格,仔细看,就会发现,图示三种分割法都经过了点(3,3)。所以我们只需要通过该点一直搜就可以。如果点碰到了边界,则说明分割完毕,总次数加一。
如图:
蓝桥杯 方格分割

  • 首先创建一个二维数组map,用来判断该点有没有障碍,该点值为1,有障碍不能走;0无障碍,能走。我们走过每一个点,都要把该点设置为障碍点,以免重复多次经过该点。且(3,3)是起始点,说明要设置map[3][3]=1。
  • 从(3,3)点开始深搜,有四个方向。每走一个方向,需要判断下一个点有没有障碍。
  • (x,y)没有障碍,则能从上一个点走到(x,y)点,然后需要将(x,y)点设置为障碍点,还需要将(x,y)的对称点(6-x,6-y)设置为障碍点(图形要对称),然后再从(x,y)点继续搜(DFS(x,y))。
  • 还需要将障碍点撤回,map[x][y]=0;
  • 最后得出的sum还需要除以4,因为旋转对称属于同一种分割法。

代码:

#include<iostream>
using namespace std;
int sum = 0;
int map[7][7];
void DFS(int x, int y) {
	if (x == 0 || y == 6 || y == 0 || x == 6) {
		sum++;
		return;
	}
	for (int i = 0; i < 4; i++) {
		if (i==0){
			if (!map[x - 1][y])
			{
				int x1 = 6 - x + 1;
				int y1 = 6 - y;
				map[x - 1][y] = map[x1][y1]=1;
				DFS(x - 1, y);
				map[x - 1][y] = map[x1][y1] = 0;
			}
			else continue;
		}
		if (i == 1) {
			if (!map[x][y + 1]) {
				int x1 = 6 - x;
				int y1 = 6 - y - 1;
				map[x][y + 1]=map[x1][y1] = 1;
				DFS(x, y + 1);
				map[x][y + 1] = map[x1][y1] = 0;
			}
			else continue;
		}
		if (i == 2) {
			if (!map[x + 1][y]) {
				int x1 = 6 - x - 1;
				int y1 = 6 - y;
				map[x + 1][y] = map[x1][y1]=1;
				DFS(x + 1, y);
				map[x + 1][y] = map[x1][y1] = 0;
			}
			else continue;
		}
		if (i == 3) {
			if (!map[x][y - 1]) {
				int x1 = 6 - x;
				int y1 = 6 - y + 1;
				map[x][y - 1] =map[x1][y1]= 1;
				DFS(x, y - 1);
				map[x][y - 1] = map[x1][y1] = 0;
			}
			else continue;
		}
	}
}
int main() {
	memset(map, 0, sizeof(map));
	map[3][3] = 1;
	DFS(3, 3);
	cout << sum / 4;
	return 0;
}
相关标签: 蓝桥杯