第十三届蓝桥杯省赛JAVAA组-矩形拼接-创新互联

✍个人博客：https://blog.csdn.net/Newin2020?spm=1011.2415.3001.5343
📚专栏地址：蓝桥杯题解集合
📣专栏定位：为想参加蓝桥别的小伙伴整理常考算法题解，祝大家都能取得理想成绩！
❤️如果有收获的话，欢迎点赞👍收藏📁，您的支持就是我创作的大动力💪

创新互联公司专注于企业营销型网站建设、网站重做改版、丰南网站定制设计、自适应品牌网站建设、H5页面制作、商城建设、集团公司官网建设、成都外贸网站建设、高端网站制作、响应式网页设计等建站业务，价格优惠性价比高，为丰南等各大城市提供网站开发制作服务。

问题描述

已知 3 个矩形的大小依次是a1×b1，a2×b2，a3×b3。用这3个矩形能拼出的所有多边形中，边数最少可以是多少？

输入格式

T 组测试，每个测试给出 6 个数据，表示 3 个矩阵。

输出格式

输出 T 行，每行一个整数，表示最少边数。

数据范围

1 ≤T≤ 1000，1 ≤a1,b1,a2,b2,a3,b3 ≤ 100。

输入样例：

2
3 2 4 1 2 4
3 2 3 1 1 1

输出样例：

4
6

思路

这道题虽然是 JAVA 组的题目，但我们仍然可以尝试用 C++ 来做，为了更快理解题意，我们模拟一下题目样例：

样例 1 给定的三个矩阵 A、B、C 的长宽分别为 3 和 2、4 和 1、2 和 4，故可以得到最优解 4，如下图所示：

样例 2 给定的三个矩阵 A、B、C 的长宽分别为 3 和 2、3 和 1、1 和 1，故可以得到最优解 6，如下图所示：

因此，我们通过画图可以发现，三个矩阵拼在一起无非就只有三种答案：

• 三个矩阵都不匹配：8 边型
• 三个矩阵能完全匹配成一个新的矩形：4 边型
• 其余情况：6 边型

又因为本题一共就三个矩形，进行任意组合就只有 2 × 3 = 6 种情况，再加上对每个矩形的长宽进行枚举也就 6 × 2 × 2 × 2 共 48 种情况，不会超时，故可以直接 6 重循环进行暴力枚举。

代码

#includeusing namespace std;
int a[3][2];
int main()
{int T;
	cin >>T;
	while (T--)
	{//输入三个矩形的长和宽
		for (int i = 0; i< 3; i++)
			cin >>a[i][0] >>a[i][1];
		int ans = 8;	//完全不匹配时的答案为8
		for (int i = 0; i< 3; i++)	//枚举第一个矩形
			for (int j = 0; j< 3; j++)
				if (i != j)	//枚举第二个矩形
					for (int k = 0; k< 3; k++)
						if (i != k && j != k)	//枚举第三个矩形
							for (int ii = 0; ii<= 1; ii++)			//枚举第一个矩形的长宽
								for (int jj = 0; jj<= 1; jj++)		//枚举第二个矩形的长宽
									for (int kk = 0; kk<= 1; kk++)	//枚举第三个矩形的长宽
									{	//第一个矩形的长等于后两个矩形的长之和
										if (a[i][ii] == a[j][jj] + a[k][kk])
										{		ans = min(ans, 6);
											//后面两个矩形的宽相等
											if (a[j][1 - jj] == a[k][1 - kk])
												ans = min(ans, 4);
										}
										//至少有一个矩形的长和第一个矩形的长相等
										if (a[i][ii] == a[j][jj] || a[i][ii] == a[k][kk])
											ans = min(ans, 6);
										//三个矩形的长全部相等
										if (a[i][ii] == a[j][jj] && a[i][ii] == a[k][kk])
											ans = min(ans, 4);
									}
		cout<< ans<< endl;
	}
	return 0;
}

你是否还在寻找稳定的海外服务器提供商？创新互联www.cdcxhl.cn海外机房具备T级流量清洗系统配攻击溯源，准确流量调度确保服务器高可用性，企业级服务器适合批量采购，新人活动首月15元起，快前往官网查看详情吧

文章题目：第十三届蓝桥杯省赛JAVAA组-矩形拼接-创新互联
转载来源：http://cdxtjz.cn/article/dosjeg.html