矩形染色问题题解

1. 题意理解

给定$T$组测试数据，每组包含$n$个矩形。每个矩形由左上角坐标$(y_1, x_1)$、右下角坐标$(y_2, x_2)$和期望颜色$c$描述。染色规则如下：

• 必须先染完一个矩形上方的所有矩形，才能染该矩形。
• 每个矩形必须一次性染完，换色时次数加1。
  目标是求出完成所有矩形染色的最少换色次数。

2. 思路分析

• 拓扑排序依据：若矩形$A$的下边界与矩形$B$的上边界重合，且$B$的左右边界覆盖$A$的左右边界，则$A$控制$B$（$B$必须在$A$之后染色）。这种依赖关系可通过拓扑排序确定染色顺序。
• 暴力搜索原因：由于$n < 15$，枚举所有可能的染色顺序（$n!$种）在时间上可行。通过深度优先搜索（DFS）遍历所有合法拓扑序，记录最小换色次数。

3. 具体实现步骤

步骤一：构建依赖关系图

1. 矩形控制条件：若矩形$i$的下边界$y_2$等于矩形$j$的上边界$y_1$，且$j$的左右边界覆盖$i$的左右边界（$j.x1 < i.x2$且$j.x2 > i.x1$），则$i$控制$j$，建立有向边$i \to j$。
2. 邻接表存储：用lin[i]存储所有被$i$控制的矩形。
3. 入度统计：in[j]表示矩形$j$的入度（即有多少个矩形控制它）。

步骤二：拓扑排序初始化

将入度为0的矩形（无依赖的矩形）作为DFS起点，因为它们可以优先染色。

步骤三：深度优先搜索枚举顺序

1. 状态定义：dfs(tot, step, nowc)表示已染$tot$个矩形，当前换色次数为$step$，上一个颜色为$nowc$。
2. 剪枝策略：若当前步骤数$step$已不小于已知最优解$ans$，直接回溯。
3. 状态转移：对于每个入度为0的矩形，染完后更新其依赖矩形的入度，并根据颜色是否变化更新换色次数。

4. 复杂度分析

• 时间复杂度：
  • 拓扑排序建图：$O(n^2)$，遍历所有矩形对判断依赖关系。
  • 暴力搜索：$O(n!)$，枚举所有可能的拓扑序，$n < 15$时$15! \approx 1.3 \times 10^{12}$，但通过剪枝可优化。
• 空间复杂度：$O(n^2)$，用于存储邻接表和入度数组。

5. 标程解析

#include <iostream>
#include <stdio.h>
#include <vector>
#include <string.h>

struct node {
    int x1, x2, y1, y2;  // 矩形坐标
    int id, c;           // 编号和颜色
};

struct node ar[21];           // 矩形数组
std::vector<int> lin[21];     // 邻接表，lin[i]存储被i控制的矩形
int ans, n, T;                // 最小换色次数、矩形数、测试用例数
int in[21];                   // 入度数组
int 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且未染色
            // 标记当前矩形为已访问，并更新依赖矩形的入度
            vis[i] = 1;
            for (int j = 0; j < lin[i].size(); j++) {
                in[lin[i][j]]--;
            }
            // 染色：颜色相同则换色次数不变，否则+1
            if (nowc == ar[i].c) {
                dfs(tot + 1, step, ar[i].c);
            } else {
                dfs(tot + 1, step + 1, ar[i].c);
            }
            // 回溯：恢复入度和访问标记
            vis[i] = 0;
            for (int j = 0; j < lin[i].size(); j++) {
                in[lin[i][j]]++;
            }
        }
    }
}

int 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++) {
                // 若i的下边界与j的上边界重合，且j覆盖i的左右边界
                if (ar[j].x1 < ar[i].x2 && ar[j].x2 > ar[i].x1 && ar[j].y1 == ar[i].y2) {
                    lin[i].push_back(j);  // i控制j
                    in[j]++;             // j的入度+1
                }
            }
        }
        // 以所有入度为0的矩形作为起点进行DFS
        for (int i = 1; i <= n; i++) {
            if (in[i] == 0 && !vis[i]) {
                vis[i] = 1;
                for (int j = 0; j < lin[i].size(); j++) {
                    in[lin[i][j]]--;
                }
                dfs(1, 1, ar[i].c);  // 染第1个矩形，换色次数+1
                vis[i] = 0;
                for (int j = 0; j < lin[i].size(); j++) {
                    in[lin[i][j]]++;
                }
            }
        }
        printf("%d\n", ans);
    }
    return 0;
}

6. 关键点说明

• 依赖关系判断：通过坐标判断矩形是否上下相邻且水平覆盖，确保拓扑序的正确性。
• DFS剪枝：当当前换色次数不小于已知最优解时提前回溯，减少无效搜索。
• 状态回溯：每次染色后恢复入度和访问标记，保证枚举所有可能的拓扑序。