Painting A Board
Time Limit: 1000MS Memory Limit: 10000K
Total Submissions: 3611 Accepted: 1795
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 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.
Input
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:
Color-code is an integer in the range of 1 .. 20.
Upper left corner of the board coordinates is always (0,0).
Coordinates are in the range of 0 .. 99.
N is in the range of 1..15.
Output
One line for each test case showing the minimum number of brush pick-ups.
Sample Input
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
Sample Output
3
Source
Tehran 1999
題目鏈接：http://poj.org/problem?id=1691
題意：
牆上有一面黑板，現劃分為多個矩形，每個矩形都要塗上一種預設顏色C。
由於塗色時，顏料會向下流，為了避免處於下方的矩形的顏色與上方流下來的顏料發生混合，要求在對矩形i著色時，處於矩形i上方直接相鄰位置的全部矩形都必須已填塗顏色。
在填塗顏色a時，若預設顏色為a的矩形均已著色，或暫時不符合著色要求，則更換新刷子，填塗顏色b。
1、 當對矩形i塗色後，發現矩形i下方的矩形j的預設顏色與矩形i一致，且矩形j上方的全部矩形均已塗色，那麼j符合填塗條件，可以用 填塗i的刷子對j填塗，而不必更換新刷子。
2、 若顏色a在之前填塗過，後來填塗了顏色b，現在要重新填塗顏色a，還是要啟用新刷子，不能使用之前用於填塗顏色a的刷子。
3、 若顏色a在剛才填塗過，現在要繼續填塗顏色a，則無需更換新刷子。
4、 矩形著色不能只著色一部分，當確認對矩形i著色後，矩形i的整個區域將被著色。
思路：
1.按照題目的規則–》拓撲排序；在矩形正上方連下方矩形一條邊；然後按顏色dfs；
if(rec[x].lx>=rec[y].lx&&rec[x].lx=rec[y].rx) return 1;
if(rec[x].rx<=rec[y].rx&&rec[x].rx>rec[y].lx) return 1;
2.dfs（num，col，step）
當col==0時即剛換刷子！
代碼：
#include
#include
#include
#include
#include
using namespace std;
struct node
{
int lx,ly,rx,ry;
int col,r;
bool flag;
int lin[15];
int now;
} rec[33];
int n;
int T;
int minn=20;
bool can(int x,int y)
{
if(rec[x].lx>=rec[y].lx&&rec[x].lx=rec[y].rx) return 1;
if(rec[x].rx<=rec[y].rx&&rec[x].rx>rec[y].lx) return 1;
return 0;
}
void cut(int x,int y)
{
for(int i=1;i<=rec[x].now;i++)
rec[rec[x].lin[i]].r+=y;
}
void dfs(int x,int c,int b)
{
if(b>=minn) return ;
if(x==n)
{
minn=min(b,minn);
return ;
}
if(c==0)
{
for(int i=1;i<=n;i++)
if(rec[i].r==0&&rec[i].flag==0)
{
rec[i].flag=1;
cut(i,-1);
dfs(x+1,rec[i].col,b);
cut(i,1);
rec[i].flag=0;
}
}
else
{
int tag=0;
for(int i=1;i<=n;i++)
if(rec[i].col==c&&rec[i].r==0&&rec[i].flag==0)
{
tag=1;
rec[i].flag=1;
cut(i,-1);
dfs(x+1,c,b);
cut(i,1);
rec[i].flag=0;
}
if(!tag) dfs(x,0,b+1);
}
}
void init()
{
for(int i=1;i<=n;i++)
{
rec[i].now=0;
rec[i].r=0;
}
for(int i=1;i<=n;i++)
{
for(int j=1;j<=n;j++)
if(i!=j&&rec[i].ry==rec[j].ly)
{
if(can(i,j)==1)
{
rec[j].r++;
rec[i].now++;
rec[i].lin[rec[i].now]=j;
}
}
}
}
int main()
{
int T;
scanf("%d",&T);
while(T--)
{
scanf("%d",&n);
minn=20;
for(int i=1;i<=n;i++)
{
scanf("%d%d%d%d%d",&rec[i].ly,&rec[i].lx,&rec[i].ry,&rec[i].rx,&rec[i].col);
}
init();
dfs(0,0,1);
printf("%d\n",minn);
}
}
