POJ1691矩形涂色问题(DFS/状态压缩DP)

### 问题描述
在给定的一组矩形中，要求使用最少的颜色数对这些矩形进行涂色，使得任意两个相邻的矩形颜色不同。每个矩形由左下角和右上角坐标以及颜色编号表示。

### 解法一：基于DFS的拓扑排序
我们首先将每个矩形抽象为图中的一个节点，如果矩形A位于矩形B上方，则在图中添加一条从A到B的有向边，并增加B的入度。接着通过拓扑排序找到所有入度为0的节点作为起点，递归地进行深度优先搜索（DFS），确保每次选择未访问且入度为0的节点进行扩展。

```cpp
#include
#include

#define MAXN 2000
#define INF 999999

struct Node {
int xl, yl, xr, yr;
int c;
} p[MAXN];

int map[20][20], in[20], n, ans, vis[20];

void build() {
memset(map, 0, sizeof(map));
memset(in, 0, sizeof(in));
memset(vis, 0, sizeof(vis));
for (int i = 0; i for (int j = 0; j if (i == j) continue;
if (p[i].yr == p[j].yl && !(p[j].xl >= p[i].xr || p[j].xr <= p[i].xl)) {
map[i][j] = 1;
in[j]++;
}
}
}
}

void DFS(int pre, int num, int sum) {
if (ans == 1) return;
if (num == n) {
if (ans > sum) ans = sum;
return;
}
for (int i = 0; i if (in[i] == 0 && !vis[i]) {
vis[i] = 1;
for (int j = 0; j if (map[i][j]) in[j]--;
}
if (p[i].c == pre)
DFS(p[i].c, num + 1, sum);
else
DFS(p[i].c, num + 1, sum + 1);
vis[i] = 0;
for (int j = 0; j if (map[i][j]) in[j]++;
}
}
}
}

int main() {
int t;
scanf("%d", &t);
while (t--) {
scanf("%d", &n);
for (int i = 0; i scanf("%d%d%d%d%d", &p[i].yl, &p[i].xl, &p[i].yr, &p[i].xr, &p[i].c);
}
build();
ans = INF;
DFS(-1, 0, 0);
printf("%d\n", ans);
}
return 0;
}
```

### 解法二：状态压缩DP
另一种方法是使用状态压缩动态规划（DP）。我们将所有可能的状态编码成二进制数，其中每一位代表是否已对该矩形进行涂色。对于每一个状态，记录当前使用的最小涂色次数。通过枚举所有状态及其子状态，更新最优解。

```cpp
#include
#include

#define INF 999999
#define min(x, y) ((x) <(y) ? (x) : (y))
#define MAXN 25

int dp[1 <<16][20];
int m[MAXN];
struct Node {
int xl, yl, xr, yr, c;
} p[MAXN];

int n;
bool check(int i, int j) {
return p[i].yr == p[j].yl && p[i].xr > p[j].xl && p[i].xl }

void build() {
memset(m, 0, sizeof(m));
for (int i = 0; i for (int j = 0; j if (check(i, j))
m[j] |= (1 < }
}
}

void get_dp() {
int state = 1 < for (int i = 0; i for (int j = 0; j dp[i][j] = INF;

for (int i = 0; i if (m[i] == 0)
dp[1 <
for (int s = 0; s for (int i = 0; i if (s & (1 < if ((s & m[i]) != m[i]) continue;
for (int j = 0; j if ((s & (1 < int t = dp[s][j];
int x = 1 < if (p[i].c != p[j].c) t++;
dp[x + s][i] = min(dp[s + x][i], t);
}
}
}

int ans = INF;
for (int j = 0; j ans = min(ans, dp[state - 1][j]);
printf("%d\n", ans);
}

int main() {
int t;
scanf("%d", &t);
while (t--) {
scanf("%d", &n);
for (int i = 0; i scanf("%d%d%d%d%d", &p[i].yl, &p[i].xl, &p[i].yr, &p[i].xr, &p[i].c);
build();
get_dp();
}
return 0;
}
```

### 总结
上述两种方法分别从图论和动态规划的角度出发，解决了矩形涂色问题。前者通过拓扑排序和DFS实现了对矩形关系的有效处理，后者则借助状态压缩技术优化了计算效率。