Preparing NOJ

喷漆机器人问题

1000ms 65536K

Description:

  F 大学开发出一种喷漆机器人Rob,能用指定颜色给一块矩形材料喷漆。Rob 每次拿起一种颜色的喷枪,为指定颜色的小矩形区域喷漆。喷漆工艺要求,一个小矩形区域只能在所有紧靠它上方的矩形区域都喷过漆后,才能开始喷漆,且小矩形区域开始喷漆后必须一次性喷完,不能只喷一部分。为Rob编写一个自动喷漆程序,使Rob拿起喷枪的次数最少。

                                                       

 

对于给定的矩形区域和指定的颜色,计算Rob 拿起喷枪的最少次数。

   

Input:

第一行有1 个正整数n1n16,表示小矩形的个数。大矩形坐标系如图所示,左上角点的坐标为(0,0)。颜色编号为正整数。接下来的n行,每行用5 个整数y1,x1,y2,x2,c来表示一个矩形。(x1,y1)(x2,y2)分别表示小矩形的左上角点坐标和右下角点坐标,c表示小矩形的颜色。

Output:

计算出Rob拿起喷枪的最少次数

Sample Input:

7
0 0 2 2 1
0 2 1 6 2
2 0 4 2 1
1 2 4 3 2
1 3 3 6 1
4 0 6 3 1
3 3 6 6 2

Sample Output:

3

Note:

 

本题由旧版NOJ导入,来源:算法设计与实验题解

Info

NOJ

Provider NOJ

Code NOJ1306

Tags

Submitted 0

Passed 0

AC Rate 0%

Date 04/20/2019 10:03:10

Related

Nothing Yet