← 返回题目
题库练习 「一本通 1.3 练习 2」平板涂色
← 上一题 下一题 →

A5638 | 「一本通 1.3 练习 2」平板涂色

时间限制1s
内存限制512MB
通过 / 提交0/0

题目描述

**原题来自：[ICPC Tehran 1999](http://poj.org/problem?id=1691)**

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

![](/uploads/acgo/image/aacea8454b43fb85_5f0310aa65f9.png)

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

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

输入格式

第一行为矩形的个数 $N$ 。
下面有 $N$ 行描述了 $N$ 个矩形。每个矩形有 $5$ 个整数描述，左上角的 $y$ 坐标和 $x$ 坐标，右下角的 $y$ 坐标和 $x$ 坐标，以及预定颜色。

输出格式

一行一个整数，表示拿起刷子的最少次数。

输入输出样例

输入 #1
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
输出 #1
3
C++ 编辑器
输入
输出