洛谷1283 平板涂色

题解

这题数据范围极小，所以直接考虑暴搜。

首先预处理一下两个块是否要满足先后关系，如果有就连一条边。判断的标准是纵坐标相等，而且横坐标上有相交的区域。

还要对每个块按照纵坐标为第一关键字，横坐标为第二关键字排序，这样可以保证对于上下颜色相等时，可以先涂完上面再继续涂下面而不会漏解。

然后进行dfs，每次搜索枚举要涂的颜色，然后把能够涂色的块都涂了。需要注意的是当前颜色和上次涂的颜色不能相等，否则没有任何意义。

剪枝就是如果当前深度大于答案或这一次涂色没有涂到任何方块就退出，个人认为很容易理解。

还有这道辣鸡题目是先输入 $y$ 节点再是 $x$ ，真的恶心。

我犯的zz错误

我是傻逼。

1. 把颜色序号和颜色名搞混
2. 把临时的 $vis2[]$ 开成全局变量

代码

struct pt{
    int x1,y1,x2,y2,col;
} s[15];
struct Edge{
    int next,to;
} edge[305];
int n,m,cnt,head[15],deg[15],ans,c[15],c2[15];
bool vis[15];

inline void add(int u,int v)
{
    edge[++cnt].to=v;
    edge[cnt].next=head[u];
    head[u]=cnt;
}

inline bool in(int x,int y) //y under x
{
    return (s[x].y2==s[y].y1 && s[x].x1<s[y].x2 && s[x].x2>s[y].x1);
}

void dfs(int x,int cur,int sum)
{
    if (x>=ans) return;
    if (sum==n)
    {
        ans=min(ans,x);
        return;
    }
    bool vis2[15];
    memcpy(vis2,vis,n+1);
    int now=0;
    for (int i=1;i<=n;i++)
    {
        if (s[i].col!=cur || vis[i]) continue;
        bool can=1;
        for (int j=head[i];j;j=edge[j].next)
        {
            int y=edge[j].to;
            if (!vis[y])
            {
                can=0;
                break;
            }
        }
        if (!can) continue;
        now++;
        vis[i]=1;
    }
    if (!now) return;
    for (int i=1;i<=m;i++)
    {
        if (c2[i]==cur) continue;
        dfs(x+1,c2[i],sum+now);
    }
    memcpy(vis,vis2,n+1);
    return;
}

inline bool cmp(pt x,pt y)
{
    return (x.y1==y.y1) ? x.x1<y.x1 : x.y1<y.y1;
}

int main()
{
    n=read();
    for (int i=1;i<=n;i++) s[i].y1=read(),s[i].x1=read(),s[i].y2=read(),s[i].x2=read(),s[i].col=read(),c[i]=s[i].col;
    sort(s+1,s+n+1,cmp);
    for (int i=1;i<=n;i++)
    {
        for (int j=1;j<=n;j++)
        {
            if (i==j) continue;
            if (in(i,j)) add(j,i);
        }
    }
    sort(c+1,c+n+1);
    for (int i=1;i<=n;i++)
    {
        if (c[i]==c[i-1]) continue;
        c2[++m]=c[i];
    }
    ans=1e9;
    for (int i=1;i<=m;i++) dfs(0,c2[i],0);
    printf("%d",ans);
    return 0;
}