【poj 1691】Painting A Board題意＆題解＆コード(C＋＋)

タイトルリンク:
http://poj.org/problem?id=1691
タイトル:
入力TはTグループデータを表す:出力nはn個の矩形を表す:次のn行、各行5個の数分、y 1,x 1,y 2,x 2,cはそれぞれその左上角座標と右下角座標を表し、座標系は題上で確立され、cはこの矩形が所望する色を表す.各矩形に所望の色を染めることが要求され、染色規則は、ある矩形に染色することができ、この矩形の上のすべての矩形が染色されている場合にのみ、染色するときは矩形全体に染色しなければならない.
問題:
题意を読み终えて、1つの矩形が制御できる矩形はその真下のすぐ隣の矩形で、毎回先に制御されていない矩形を塗らなければならなくて、トポロジーのソートを考えたようで、色を変える回数を最小にして、データの范囲nを観察して15より小さくて、ああ、葛藤しないで、断固として暴力的に色を涂ります.
コード:

#include
#include
#include
#include
#include
using namespace std;
struct node{
    int x1,x2,y1,y2;
    int id,c;
}ar[21];
vector<int>lin[21];
int ans,n,T,in[21],vis[21];
void dfs(int tot,int step,int nowc)
{
    if (step>=ans) return ;
    if (tot==n)
    {
        ans=step;
        return ;
    }
    for (int i=1;i<=n;i++)
    if (in[i]==0&&vis[i]==0)
    {
        for (int j=0;j1;
        if (nowc==ar[i].c)
        dfs(tot+1,step,nowc);
        else
        dfs(tot+1,step+1,ar[i].c);
        vis[i]=0;
        for (int j=0;jint main()
{
    scanf("%d",&T);
    while(T--)
    {
        scanf("%d",&n);
        ans=999999;
        for (int i=1;i<=n;i++)
        {
            scanf("%d%d%d%d%d",&ar[i].y1,&ar[i].x1,&ar[i].y2,&ar[i].x2,&ar[i].c);
            ar[i].id=i;
            lin[i].clear();
            in[i]=0;vis[i]=0;
        }
        //  ，       
        for (int i=1;i<=n;i++)
        for (int j=1;j<=n;j++)
        if (ar[j].x1ar[i].x1&&ar[j].y1==ar[i].y2)
        {   
            lin[i].push_back(j);
            in[j]++;
        }
        for (int i=1;i<=n;i++)
        if (in[i]==0&&vis[i]==0)
        {
            vis[i]=1;
                    for (int j=0;j1,1,ar[i].c);
            vis[i]=0;
                    for (int j=0;jprintf("%d
",ans);
    }
}