能否完美拼成矩形

题目：给定一个N行4列的二维数组matrix,表示N个每条边不是平行于X轴就是平行于Y轴的矩形，想知道所有的矩形能否组成一个大的完美矩形。完美矩形是指拼出的整体图案是矩形，既不缺任何块，也没有重合的部分。

思路：1、每一个小矩形的面积累加起来必须是等于大矩形的面积  2、除大矩形的四个顶点只出现一次之外，其它任何小矩形的顶点都必须出现偶数次。

def isRectangleCover(matrix):import sysif len(matrix) == 0 or len(matrix[0]) == 0:return FalsemostLeft = sys.maxsizemostRight = -sys.maxsizemostDown = sys.maxsizemostUp = -sys.maxsizemap_ = {}area = 0for rect in matrix:mostLeft = min(rect[0],mostLeft)mostDown = min(rect[1],mostDown)mostRight = max(rect[2],mostRight)mostUp = max(rect[3],mostUp)area += (rect[2]-rect[0]) * (rect[3] - rect[1])leftDown = rect[0] + '_' + rect[1]leftUp = rect[0] + '_' + rect[3]rightDown = rect[2] + '_' + rect[1]rightUp = rect[2] + '_' + rect[3]if !map_.add(leftDown):map.remove(leftDown)if !map_.add(leftUp):map.remove(leftUp)if !map_.add(rightDown):map.remove(rightDown)if !map_.add(rightUp):map.remove(rightUp)if(mostLeft + '_' + mostDown not in map_ or mostLeft + '_' + mostUp not in map_ or mostRight + '_' + mostDown not in map_ ormostRight + '_' + mostUp not in map_ orlen(map_)!=4):return Falsereturn area == (mostRight - mostLeft) * (mostUp - mostDown)

 

总结

以上是生活随笔为你收集整理的能否完美拼成矩形的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。