第十三届蓝桥杯省赛 JAVA A组 - 矩形拼接

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

问题描述

已知 3 个矩形的大小依次是a1×b1a2×b2a3×b3。用这3个矩形能拼出的所有多边形中边数最少可以是多少

输入格式

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

输出格式

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

数据范围

1 ≤ T ≤ 10001 ≤ 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 重循环进行暴力枚举。

代码

#include<bits/stdc++.h>
using 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;
}