首页 > 试题广场 >

能否完美地拼成矩形

[编程题]能否完美地拼成矩形
  • 热度指数：523 时间限制：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

备注:

算法知识视频讲解
添加回答
JavaScript
牛客990759816号头像 牛客990759816号
思路:1.通过面积相等判断不缺任何块儿且不重合 2.通过判断单元块(1x1)是否在前只在一个矩形内,来判断是否缺块儿 
class FormRectangle{
private minLeft:number;
private maxRight:number;
private maxTop:number;
private minBottom:number;
public constructor(){
const matrix:number[][] = str.split(/\n/g).map((l)=>{
return l.split(/ /g).map(a=>Number(a));
});
console.log(matrix);
if(this.udgmentArea(matrix) && this.udgmentBlock(matrix)){
console.log('Yes');
}else{
console.log('No');
}
}
/**
* 判断面积
* @param {*} matrix
* @returns
*/
private udgmentArea(matrix:number[][]){
const firstRow = matrix[0];
let minLeft = firstRow[0];
let maxRight = firstRow[2];
let maxTop = firstRow[3];
let minBottom = firstRow[1];
let area = 0;
for(const row of matrix){
minLeft = Math.min(minLeft, row[0]);
maxRight = Math.max(maxRight, row[2]);
maxTop = Math.max(maxTop, row[3]);
minBottom = Math.min(minBottom, row[1]);
area += (row[2] - row[0]) * (row[3] - row[1]);
}
this.minLeft = minLeft;
this.maxRight = maxRight;
this.maxTop = maxTop;
this.minBottom = minBottom;
const maxarea = (maxTop - minBottom) * (maxRight - minLeft);
console.log( `${maxarea} === ${area}`);
return maxarea === area;
}
/**
* 通过判断单元块(1x1)是否在前只在一个矩形内
* @param matrix
* @returns
*/
private udgmentBlock(matrix:number[][]){
const minLeft = this.minLeft;
const maxRight = this.maxRight;
const maxTop = this.maxTop;
const minBottom = this.minBottom;
const rows = new Array(maxRight - minLeft).fill(1).map((val, index)=>{ return minLeft + index + 0.5;});
const rols = new Array(maxTop - minBottom).fill(1).map((val, index)=>{ return minBottom + index + 0.5;});
const list = [];
rows.forEach((a)=>{
rols.forEach((b)=>{
list.push([a, b]);
});
});
const m = new Array(matrix.length).fill(0);
return list.every((a:number[])=>{
return this.inBox(a, m, matrix);
});
}
/**
* 判断点 point 是否在matrix中的一个小块内
* @param point
* @param matrix
* @returns
*/
private inBox(point:number[], m:number[], matrix:number[][]){
const index = matrix.findIndex((r, index)=>{
if(m[index] === 0){
const [a, b, c, d] = r;
const [x, y] = point;
return (x - a) * (x - c) < 0 && (y - b) * (y - d) < 0;
}
return false;
});
// 去掉单元块,以减少比较次数 ,(容易出错, 最好改用标志位的形式)
const [a, b, c, d] = matrix[index];
// console.log([a, b, c, d], matrix, index);
if(index !== -1 && c - a === 1 && d - b === 1){
m[index] = 1;
}
return index !== -1;
}
}

发表于 2022-04-09 16:47:56 回复(0)
提交观点

问题信息

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

热门推荐

通过挑战的用户

查看代码

相关试题

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

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