首页 > 试题广场 >

能否完美地拼成矩形

[编程题]能否完美地拼成矩形
  • 热度指数：526 时间限制：C/C++ 2秒，其他语言4秒 空间限制：C/C++ 256M，其他语言512M
  • 算法知识视频讲解
每条边不是平行于X轴就是平行于Y轴的矩形，可以用左下角和右上角的点来表示。比如{1, 2, 3, 4}，表示的图形如下

给定一个N行4列的二维数组matrix，表示N个每条边不是平行于X轴就是平行于Y轴的矩形。想知道所有的矩形能否组成一个大的完美矩形。完美矩形是指拼出的整体图案是矩形，既不缺任何块儿，也没有重合部分
[要求]
时间复杂度为，额外空间复杂度为

输入描述:
第一行一个整数N，表示matrix的行数
接下来N行，每行4个整数分别表示矩形的左下角和右上角的点


输出描述:
若可以拼成一个大的完美矩形，输出"Yes", 否则输出"No"
示例1

输入

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

输出

No

说明

缺少{2, 3, 3, 4}这一块儿
示例2

输入

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

输出

No

说明

拼出的图案缺少{3, 1, 4, 2}，并且{3, 2, 4, 2}是重合区域
示例3

输入

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

输出

Yes

备注:

算法知识视频讲解
开通博客
头像 星晨
发表于 2020-11-29 15:42:13
完美矩形： N 个小矩形可以完美拼接成一个大矩形，不缺，不重重点在于如何保证不缺和不重复 先对所有的输入进行遍历找到 最终的左下角，右上角 检查如果有超越，左右点的边界的 则舍弃 检查是否为完美矩形（除了标记，每个端点必然完全重合，而且是两次） package main import ( 展开全文
去ta的博客 赞 (0) 回复(0) 收起

问题信息

数学 思维 基础数学
上传者：小小
难度：
3条回答 4123浏览

热门推荐

通过挑战的用户

查看代码

相关试题

能否完美地拼成矩形

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

扫描二维码，关注牛客公众号