蓝桥杯 方格分割
程序员文章站
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;
}