程序師世界是廣大編程愛好者互助、分享、學習的平台,程序師世界有你更精彩!
首頁
編程語言
C語言|JAVA編程
Python編程
網頁編程
ASP編程|PHP編程
JSP編程
數據庫知識
MYSQL數據庫|SqlServer數據庫
Oracle數據庫|DB2數據庫
 程式師世界 >> 編程語言 >> C語言 >> C++ >> C++入門知識 >> [poj 1691] Painting A Board dfs+拓撲排序

[poj 1691] Painting A Board dfs+拓撲排序

編輯:C++入門知識

[poj 1691] Painting A Board dfs+拓撲排序


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);
    }

}

  1. 上一頁:
  2. 下一頁:
Copyright © 程式師世界 All Rights Reserved