2 shunfurh shunfurh 于 2017.09.15 10:07 提问

Painting A Board

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 C. The APM picks one brush with color C and paints all possible rectangles having predefined color C 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 F in Figure 1 is painted only after rectangles C and D 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.


The first line of the input file contains an integer M which is the number of test cases to solve (1 <= M <= 10). For each test case, the first line contains an integer N, the number of rectangles, followed by N lines describing the rectangles. Each rectangle R is specified by 5 integers in one line: the y and x coordinates of the upper left corner of R, the y and x coordinates of the lower right corner of R, followed by the color-code of R.

Note that:

  1. Color-code is an integer in the range of 1 .. 20.

  2. Upper left corner of the board coordinates is always (0,0).

  3. Coordinates are in the range of 0 .. 99.

  4. N is in the range of 1..15.


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

Sample Input

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

Sample Output



caozhy   Ds   Rxr 2017.09.16 10:53
shen_wei   Ds   Rxr 2017.09.15 16:10
Csdn user default icon
poj1691 Painting A Board
链接:http://poj.org/problem?id=1691 题意:
【poj 1691】Painting A Board 题意&题解&代码(C++)
poj dfs
poj1691——Painting A Board
题目大意:给一个包含N个矩形的板子上色,每个矩形的颜色已经确定,给一个矩形上色时,必须满足它上方的所有矩形已经上色结束,一个刷子只能用一次且涂满整个矩形,问最少需要多少个刷子 输入:case个数M (1            第i个case的矩形个数N(1            N个矩形的描述(左上角坐标y  x  右下角坐标y  x(坐标0~99横坐标x纵坐标y)  颜色代码(代码1~2
zoj1424 Painting A Board
#include #include struct node { int x1,x2,y1,y2,code; }rec[15]; int map[15][15],ru[15],vis[15],n,minn; bool pan(int i,int j) { if(rec[i].y2==rec[j].y1&&!(rec[i].x2rec[j].x2)) return true; else re
Painting A Board poj1691
题目大意:给定一个矩形区域,其中又分为了n个形状大小不同的矩形区域,要对每个矩形进行染色,其中一个矩形可以染色的前提是其上面的矩形已经染完色了,因为染一个小矩形需要的颜色不同所以要不断的变换画刷的颜色,所以可以将一些满足题意的颜色相同的矩形放在一块进行染色,求最少画刷换的次数。 解题思路:建图,进行深艘,将每个小矩形的缩为一个点,其上面的和其紧邻着的没有染色的矩形的个数称为小矩形的度,如果它的度
POJ-1691 Painting A Board
Time Limit: 1000MS   Memory Limit: 10000K Total Submissions: 3616   Accepted: 1798 Description The CE digital company has built an Automatic Painting Machine (APM) to paint a flat
POJ1691–Painting A Board 测试数据
POJ1691–Painting A Board 测试数据。数据开源:Tehran 1999 问题B
codeforces 922 C Cave Painting
能同时满足n mod i = i -1 (i = 1, 2, 3, ..., k)的n有多少个呢?
zoj 1610 Count the Colors 线段树,成段更新染色
Count the ColorsTime Limit:2000MS    Memory Limit:65536KB    64bit IO Format:%lld & %llu SubmitStatus Description Painting some colored segments on a line, some previously painted segments may
Codeforces Round #461 (Div. 2) C. Cave Painting(数论 思维)
C. Cave Paintingtime limit per test1 secondmemory limit per test256 megabytesinputstandard inputoutputstandard outputImp is watching a documentary about cave painting.Some numbers, carved in chaotic o...