## 题目描述：

LeetCode 391. Perfect Rectangle

Given N axis-aligned rectangles where N > 0, determine if they all together form an exact cover of a rectangular region.

Each rectangle is represented as a bottom-left point and a top-right point. For example, a unit square is represented as [1,1,2,2]. (coordinate of bottom-left point is (1, 1) and top-right point is (2, 2)).

Example 1:

```rectangles = [
[1,1,3,3],
[3,1,4,2],
[3,2,4,4],
[1,3,2,4],
[2,3,3,4]
]

Return true. All 5 rectangles together form an exact cover of a rectangular region.
```

Example 2:

```rectangles = [
[1,1,2,3],
[1,3,2,4],
[3,1,4,2],
[3,2,4,4]
]

Return false. Because there is a gap between the two rectangular regions.
```

Example 3:

```rectangles = [
[1,1,3,3],
[3,1,4,2],
[1,3,2,4],
[3,2,4,4]
]

Return false. Because there is a gap in the top center.
```

Example 4:

```rectangles = [
[1,1,3,3],
[3,1,4,2],
[1,3,2,4],
[2,2,4,4]
]

Return false. Because two of the rectangles overlap with each other.
```

## 解题思路：

https://discuss.leetcode.com/topic/55923/o-n-solution-by-counting-corners-with-detailed-explaination

```左下顶点A的坐标为(l, b)

```        G
D |-----|-----| C
|     |     |
H |-----I-----| F
|     |     |
A |-----|-----| B
E
```

```points[A] |= 1
points[B] |= 2
points[C] |= 4
points[D] |= 8

points[E] = points[A] | points[B] = 3 （左下顶点、右下顶点的并）
points[F] = points[B] | points[C] = 6 （右下顶点、右上顶点的并）
points[G] = points[C] | points[D] = 12 （右上顶点、左上顶点的并）
points[H] = points[A] | points[D] = 9 （左下顶点、左上顶点的并）
points[I] = points[A] | points[B] | points[C] | points[D] = 15（四个顶点的并）```

## Python代码：

``````class Solution(object):
def isRectangleCover(self, rectangles):
"""
:type rectangles: List[List[int]]
:rtype: bool
"""
left = min(x[0] for x in rectangles)
bottom = min(x[1] for x in rectangles)
right = max(x[2] for x in rectangles)
top = max(x[3] for x in rectangles)

points = collections.defaultdict(int)
for l, b, r, t in rectangles:
A, B, C, D = (l, b), (r, b), (r, t), (l, t)
for p, q in zip((A, B, C, D), (1, 2, 4, 8)):
if points[p] & q: return False
points[p] |= q

for px, py in points:
if left < px < right or bottom < py < top:
if points[(px, py)] not in (3, 6, 9, 12, 15):
return False
return True
``````

Pingbacks已关闭。

1. 赤壁的火神 发布于 2016年8月30日 01:06 #

我想知道这道题这样的思路是怎么想出来的。。。自己做的时候这道题真是毫无头绪

2. Leo 发布于 2016年9月1日 14:14 #

第一个解法还是会报错。。。
我用了一个非常笨的解法 等于是先去检查四条边 然后检查内部没有overlap 然后再检查面积

3. 在线疯狂 发布于 2016年9月1日 15:02 #

感谢提醒！解法I无法通过[[0,0,1,1],[0,0,1,1],[1,1,2,2],[1,1,2,2]]，已经修改！