pku1691 Painting A Board

#include<stdio.h>

const int INF=1000000;
int g[16][16],n;
bool visit[16];
struct Node
{
    int x1,x2,y1,y2;
};
Node node[16];

int dfs(int color,int count)    //count记录用刷子的次数

{
    int ans=INF;
    for(int i=1;i<=n;i++)
    {
        if(!visit[i]&&g[0][i]==0)
        {
            visit[i]=1;
            if(g[i][0]!=color) count++;
            for(int j=1;j<=n;j++) if(g[i][j]) g[0][j]--;
            
            int k=dfs(g[i][0],count);     
            if(k<ans) ans=k;

            visit[i]=0;    //回溯是为了改变当前入度为0的长方形的涂色顺序，即使当前入度为0的长方形成全排列

            for(int j=1;j<=n;j++) if(g[i][j]) g[0][j]++;
            if(g[i][0]!=color) count--;        
        }
    }
    if(ans==INF) ans=count;
    return ans; //仅有的return返回n个长方形已完成的若干次排列所需的刷子的最少次数

}

int main()
{
    int cases;
    scanf("%d",&cases);
    while(cases--)
    {
        scanf("%d",&n);
        for(int i=0;i<=n;i++)
        {
            visit[i]=0;
            for(int j=0;j<=n;j++) g[i][j]=0;
        }
        for(int i=1;i<=n;i++)        
        {
            scanf("%d%d%d%d%d",&node[i].x1,&node[i].y1,&node[i].x2,&node[i].y2,&g[i][0]);        
            for(int j=1;j<i;j++)
            {
                if(node[i].x2==node[j].x1&&!(node[i].y1>=node[j].y2||node[i].y2<=node[j].y1))
                {
                    g[i][j]=1;g[0][j]++;
                }
                if(node[j].x2==node[i].x1&&!(node[j].y1>=node[i].y2||node[j].y2<=node[i].y1))
                {
                    g[j][i]=1;g[0][i]++;
                }
            }
        }
        printf("%d\n",dfs(-1,0));
    }
    return 0;
}


总结：

最开始想通过拓扑的形式从上向下选择，但是超时，其实用dfs构图也用到了拓扑的思想