当前位置: 首页 > article >正文

方格分割(蓝桥杯2017年试题D)

【问题描述】

     6*6的方格,沿着格子的边线剪开成两部分,要求这两部分的形状完全相同。如下图所示,p1.png、p2.png、p3.png就是可行的分割法。

     试计算:包括这三种分法在内,一共有多少种不同的分割方法。

 注意:旋转对称的图形属于同一种分割方法。

【参考答案】

  509

【解析】

       这是一道典型的深度优先搜索题目。但应从何处开始搜索呢?通过观察样例图案可以发现,如果把样例图案剪开,则会有且只有两个点在边界上,且一定经过中心点(3,3)。如果以中心点(3,3)为起点进行深搜,每搜索一个点,根据对称关系,再标记其对称点,该题就可以得到解决了。

       具体的注意点有以下三个。

     (1)最后搜索结果

         根据题意,由于旋转对称的图形属于同一种分割方法,因此最后要将得到的结果除以4,以解决四个顶点的对称性。

       (2)标记对称点

         当搜索一个点时,必须要有一个对称点不能被搜索,即形状的另一个部分。如果搜索点的坐标是(x,y),则根据中心对称,对称点的坐标是(6-x,6-y)。

      (3)搜索方向

       可以向四个方向进行搜索:向右、向左、向上、向下,这里采用方向数组 dx和dy表示。

      int dx[4] = {-1,1,0,0};    int dy[4] = {0,0,-1,1}

【参考程序如下】

#include <iostream>
using namespace std;
int dx[] = {-1,1,0,0};
int dy[] = {0,0,-1,1};
const int N = 6;
bool visited[N + 1] [N + 1];
int ans = 0;
void dfs(int x,int y)
{
	if(x == 0 || x == N || y == 0 || y == N)
	{
		ans++;
		return;
	}
	for(int i = 0; i < 4; i++)
	{
		int nx = x + dx[i];
		int ny = y + dy[i];
		if(!visited[nx][ny])
		{
			visited[nx][ny] = true;
			visited[N - nx] [N - ny] = true;
			dfs(nx,ny);
			visited[N - nx] [N - ny] = false;
			visited[nx][ny] = false;
		}
	}
}
int main(int argc, char** argv) {
	visited[N / 2] [N / 2] = true;
	dfs(N / 2,N / 2);
	cout << ans / 4;
	return 0;
}

【程序运行结果如下】


http://www.kler.cn/a/447378.html

相关文章:

  • 如何测量分辨率
  • HUAWEI-eNSP交换机链路聚合(手动负载分担模式)
  • MacOS安装MySQL
  • 大数据面试题--企业面试真题
  • HIPT论文阅读
  • 感受野如何计算?
  • 台球助教系统开发之助教预约功能模块需求分析(第十三章)
  • 【Python】利用函数模拟创建【栈】的数据结构操作
  • MFC/C++学习系列之简单记录6
  • Kubeadm+Containerd部署k8s(v1.28.2)集群(非高可用版)
  • Pytorch | 利用NI-FGSM针对CIFAR10上的ResNet分类器进行对抗攻击
  • go-zero负载均衡实现原理
  • 重拾设计模式--模板方法模式
  • 书生·浦语大模型全链路开源体系-第6关 OpenCompass 评测
  • 苹果手机怎么清理空间:拯救你的拥挤手机
  • MyBatis主键自增回填功能源码分析
  • Redis List操作
  • Docker容器命令
  • clickhouse-副本和分片
  • StarRocks:存算一体模式部署
  • maui开发成生安卓apk,运行提示该应用与此设备的CPU不兼容
  • Spring Boot + Dubbo 的整合 ,仅需六步
  • Redis 初相识:开启缓存世界大门
  • 四川XX信息技术职业学院教案
  • react概念篇
  • 巧用AI显著提升工作和学习的效率和质量