Painting A Board --FOJ 1691

时间：2010-10-13 来源：勇泽

1、题目类型：暴力法、DFS。

2、解题思路：题意，一块大的矩形区域的被分成多个矩形区域，现在要给不同的区域涂上不同的颜色，有不同颜色的刷子可以提供，每个刷子可以刷一种不同的颜色。每刷一次，将刷尽可能多的矩形区域。由于涂色的油漆会下滑，只有在一个区域的上部直接相邻的区域被刷了之后才能给这个区域刷。问该如何涂色使得切换刷子的次数最少。步骤：（1）根据输入建立结构体Ret，记录其区域位置及其该涂抹的颜色：（2）暴力法从每一种满足check条件（即该区域的上面区域是否已经被涂抹）的区域开始涂抹；（3）运用DFS回溯法查找其所需要切换刷子次数，对比获得最小的次数为最优。

3、注意事项：注意DFS的结束条件判断。

4、实现方法:

#include<iostream>
#include<algorithm>
using namespace std;

struct Ret{
    int x1,x2;
    int y1,y2;
    int col;
};

int n,ans;
Ret ret[20];
bool mark[110][110],vis[20];

bool Check(int p)
{
    int i;    
    for(i=ret[p].y1;i<=ret[p].y2;i++)
        if(!mark[ret[p].x1][i])
            return false;
    return true;
}

void DFS(int pos,int cnt,int rcnt)
{
    int i,j;
    if(rcnt==n)
    {
        if(ans>cnt)    ans=cnt;
        return ;
    }
    vis[pos]=1;
    for(j=ret[pos].y1;j<=ret[pos].y2;j++)
        mark[ret[pos].x2][j]=1;
    for(int i=0;i<n;i++)
    {
        if(!vis[i] && Check(i))
        {
            if(ret[pos].col==ret[i].col)
                DFS(i,cnt,rcnt+1);
            else
                DFS(i,cnt+1,rcnt+1);
        }
    }
    for(j=ret[pos].y1;j<=ret[pos].y2;j++)
        mark[ret[pos].x2][j]=0;
    vis[pos]=0;
}

void Solve()
{
    int i,an=9999999;
    for(i=0;i<n;i++)
    {
        ans=9999999;
        memset(vis,0,sizeof(vis));
        if(Check(i))
            DFS(i,1,1);    
        if(an>ans)
            an=ans;
    }
    cout<<an<<endl;
}

int main()
{
    int i,T;
    cin>>T;
    while(T--)
    {
        cin>>n;
        memset(mark,0,sizeof(mark));
        for(i=0;i<n;i++)
        {
            cin>>ret[i].x1>>ret[i].y1>>ret[i].x2>>ret[i].y2>>ret[i].col;
        }
        for(i=0;i<=100;i++)
            mark[0][i]=1;
        Solve();
    }
    return 0;
}