平板涂色
时间限制:1秒 内存限制:256M
【问题描述】
CE数码公司开发了一种名为自动涂色机(APM)的产品。它能用预定的颜色给一块由不同尺寸且互不覆盖的矩形构成的平板涂色。
为了涂色,APM需要使用一组刷子。每个刷子涂一种不同的颜色 \(C\)。APM拿起一把有颜色 \(C\) 的刷子,并给所有颜色为 \(C\) 且符合下面限制的矩形涂色:为了避免颜料渗漏使颜色混合,一个矩形只能在所有紧靠它上方的矩形涂色后,才能涂色。例如图中矩形 \(F\) 必须在 \(C\) 和 \(D\) 涂色后才能涂色。注意,每一个矩形必须立刻涂满,不能只涂一部分。 写一个程序求一个使APM拿起刷子次数最少的涂色方案。注意,如果一把刷子被拿起超过一次,则每一次都必须记入总数中。
【输入格式】
第一行为矩形的个数 \(N\)。下面有 \(N\) 行描述了 \(N\) 个矩形。每个矩形有 5 个整数描述,左上角的 \(y\) 坐标和 \(x\) 坐标,右下角的 \(y\) 坐标和 \(x\) 坐标,以及预定颜色。颜色号为 1 到 20 的整数。平板的左上角坐标总是 (0,0)。
【输出格式】
拿起刷子的最少次数。
【输入输出样例】
Input
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
Output
3
【数据说明】
对于 \(100\%\) 的数据 坐标的范围是 0..99,\(N\) 小于 16。。
【来源】
Mr.he