33OJ
登录 注册

#P1283. [ICPC 1999 Tehran R] 平板涂色

[ICPC 1999 Tehran R] 平板涂色

Problem Description

The CE digital company has built an Automatic Painting Machine (APM) to paint a flat board fully covered by adjacent non-overlapping rectangles of different sizes each with a predefined color.

To color the board, the APM has access to a set of brushes. Each brush has a distinct color CC. The APM picks one brush with color CC and paints all possible rectangles having predefined color CC with the following restrictions:

To avoid leaking the paints and mixing colors, a rectangle can only be painted if all rectangles immediately above it have already been painted. For example rectangle labeled FF in Figure 11 is painted only after rectangles CC and DD are painted. Note that each rectangle must be painted at once, i.e. partial painting of one rectangle is not allowed.

You are to write a program for APM to paint a given board so that the number of brush pick-ups is minimum. Notice that if one brush is picked up more than once, all pick-ups are counted.

Input Format

The first line contains an integer NN, the number of rectangles, followed by NN lines describing the rectangles. Each rectangle RR is specified by 55 integers in one line: the yy and xx coordinates of the upper left corner of RR, the yy and xx coordinates of the lower right corner of RR, followed by the color-code of RR.

Output Format

One line for each test case showing the minimum number of brush pick-ups.

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

3

Hint

Constraints: 1≤Ci≤201 \le C_i \le 20, 0≤xi,yi≤990 \le x_i, y_i \le 99, 1≤N≤161 \le N \le 16.