方格分割（蓝桥杯）

文章目录

方格分割
- 题目描述
- 答案：509
- 思路
- dfs

方格分割

题目描述

本题为填空题，只需要算出结果后，在代码中使用输出语句将所填结果输出即可。

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

如下就是三种可行的分割法。

在这里插入图片描述

答案：509

思路

在这里插入图片描述
首先，从题目入手，一个方格纸分割成两个相同的部分，首先可以想到剪“格子”，但是剪“格子”这种方法不好判断连通的问题，所以应该换一个思路，换成找切割线，由于是两个相同的部分，所以切割线是关于中心点中心对称的，由线再化到点上去，就转化成了遍历点的思路，我们可以利用深搜（DFS）来遍历寻找切割方法的总数；

截至条件为切割到纸的边界处也就是：（x==0||y==0||x==6||y==6）
设置记忆数组将每次遍历的点做标记，便于判断是否遍历过

注意：题目中说旋转，对称算作一种图形，图案关于中心点中心对称的所以应该除以4

在这里插入图片描述

dfs

这段代码是一个C++程序，用于解决一个方格分割问题。下面是对代码的详细注释：

// 引入所有标准库
#include<bits/stdc++.h>
using namespace std;// 定义一个二维数组v[7][7]，用于标记6x6的方格是否被访问过，初始化为0
int v[7][7];// 定义一个整数ans，用于记录分割方法的数量
int ans;// 定义两个数组dx和dy，分别表示在x和y方向上的移动，用于搜索周围的格子
int dx[]={-1,1,0,0};
int dy[]={0,0,-1,1};// 定义一个辅助函数check，用于判断某个格子是否在6x6的范围内且未被访问过
bool check(int x,int y)
{if(x>=0&&x<=6&&y>=0&&y<=6&&v[x][y]==0) // 判断x和y是否在[0,6]范围内，并且v[x][y]为0return true; // 如果是，则返回truereturn false; // 否则返回false
}// 定义一个递归函数dfs，用于深度优先搜索分割方格的所有可能情况
void dfs(int x,int y)
{if(x==0||x==6||y==0||y==6) // 如果当前格子位于边界上{ans++; // 增加分割方法的数量return ; // 直接返回，不再继续搜索}for(int i=0;i<4;i++) // 遍历四个方向{int tox=x+dx[i]; // 计算下一个格子的x坐标int toy=y+dy[i]; // 计算下一个格子的y坐标if(check(tox,toy)) // 如果下一个格子在范围内且未被访问过{v[tox][toy]=1; // 标记当前格子为已访问v[6-tox][6-toy]=1; // 由于分割后的两部分形状完全相同，所以同时标记对称位置的格子dfs(tox,toy); // 递归调用dfs，继续搜索下一个格子v[tox][toy]=0; // 回溯，取消当前格子的访问标记v[6-tox][6-toy]=0; // 同时取消对称位置格子的访问标记}}
}int main()
{v[3][3]=1; // 初始化方格，将中心点标记为已访问，这是题目给定的初始条件dfs(3,3); // 调用dfs函数，从(3,3)开始深度优先搜索cout<<ans/4; // 输出分割方法的数量，由于每4种旋转对称的分割方法视为一种，所以需要除以4return 0; // 程序结束
}