问题 2157 --平板涂色

2157: 平板涂色★★★

时间限制: 1 Sec  内存限制: 128 MB
提交: 52  解决: 39
[提交][状态][命题人:]

题目描述

CE 数码公司开发了一种名为自动涂色机(APM)的产品。它能用预定的颜色给一块由不同尺寸且互不覆盖的矩形构成的平板涂色。

为了涂色,APM 需要使用一组刷子。每个刷子蘸了颜色 CCC 。APM 拿起一把蘸有颜色 CCC 的刷子,并给所有颜色为 CCC 的矩形涂色。请注意,涂色有顺序要求:为了避免颜料渗漏使颜色混合,一个矩形只能在所有紧靠它上方的矩形涂色后,才能涂色。例如图中矩形 FFF 必须在 CCC  DDD 涂色后才能涂色。注意,每一个矩形必须立刻涂满,不能只涂一部分。

写一个程序求一个使 APM 拿起刷子次数最少的涂色方案。注意,如果一把刷子被拿起超过一次,则每一次都必须记入总数中。


输入

第一行为矩形的个数 NNN 
下面有 NNN 行描述了 NNN 个矩形。每个矩形有 555 个整数描述,左上角的 yyy 坐标和 xxx 坐标,右下角的 yyy 坐标和 xxx 坐标,以及预定颜色。

输出

一行一个整数,表示拿起刷子的最少次数。
样例输入
Copy
7
0 0 2 2 1
0 2 1 6 2
2 0 4 2 1
1 2 4 4 2
1 4 3 6 1
4 0 6 4 1
3 4 6 6 2
样例输出
Copy
3

提示

来源

 

[提交][状态]