题意：一个 n x m 的矩形(1 <= n, m <= 30)，现给出这个矩形中 p 个（1 <= p <= 500）子矩形的左下角与右下角坐标，问最少用多少个子矩形能够恰好组成这个 n x m 的大矩形。
题目链接：
——>>这是精确覆盖问题，而DLX正是解决精确覆盖问题的有利武器。。
模型转换：将原矩形变成一行，作为 DLX 中的列，表示要被覆盖一次且仅一次的目标。子矩形则是行中的一些点，每一个子矩形作为 DLX 的一行，它所覆盖行中的点的位置标为1，其余位标为0，则问题转化为：选出最少的行，使得选出的行中每一列有且仅有一个1，这正是 DLX 解决的问题。。
注：在往下一层 dfs 的时候，假设检測返回值为真，可别来个return true，这时会中断后面的搜索（非常隐秘地 WA 了几发
）。。为了方便，我不要返回值了。。
为了加快搜索，能够来个剪枝，dfs 时检測当前深度是否 >= 已搜索到的可满足要求的长度。。
#include#include const int MAXN = 30 + 10;const int MAXR = 500 + 10;const int MAXC = 30 * 30 + 10;const int MAXNODE = MAXR * MAXC;const int INF = 0x3f3f3f3f;struct DLX{ int sz; int H[MAXR], S[MAXC]; int row[MAXNODE], col[MAXNODE]; int U[MAXNODE], D[MAXNODE], L[MAXNODE], R[MAXNODE]; int Min; void Init(int n) { for (int i = 0; i <= n; ++i) { U[i] = D[i] = i; L[i] = i - 1; R[i] = i + 1; } L[0] = n; R[n] = 0; sz = n + 1; memset(S, 0, sizeof(S)); memset(H, -1, sizeof(H)); } void Link(const int& r, const int& c) { row[sz] = r; col[sz] = c; D[sz] = D[c]; U[D[c]] = sz; D[c] = sz; U[sz] = c; if (H[r] == -1) { H[r] = L[sz] = R[sz] = sz; } else { R[sz] = R[H[r]]; L[R[H[r]]] = sz; R[H[r]] = sz; L[sz] = H[r]; } S[c]++; sz++; } void Remove(const int& c) { L[R[c]] = L[c]; R[L[c]] = R[c]; for (int i = D[c]; i != c; i = D[i]) { for (int j = R[i]; j != i; j = R[j]) { U[D[j]] = U[j]; D[U[j]] = D[j]; S[col[j]]--; } } } void Restore(const int& c) { for (int i = U[c]; i != c; i = U[i]) { for (int j = L[i]; j != i; j = L[j]) { S[col[j]]++; U[D[j]] = j; D[U[j]] = j; } } L[R[c]] = c; R[L[c]] = c; } void Dfs(int cur) { if (cur >= Min) return; if (R[0] == 0) { if (cur < Min) { Min = cur; } return; } int c = R[0]; for (int i = R[0]; i != 0; i = R[i]) { if (S[i] < S[c]) { c = i; } } Remove(c); for (int i = D[c]; i != c; i = D[i]) { for (int j = R[i]; j != i; j = R[j]) { Remove(col[j]); } Dfs(cur + 1); for (int j = L[i]; j != i; j = L[j]) { Restore(col[j]); } } Restore(c); } void Solve() { Min = INF; Dfs(0); Min != INF ? printf("%d\n", Min) : puts("-1"); }} dlx;int ReadInt(){ int ret = 0; char ch; while ((ch = getchar()) && ch >= '0' && ch <= '9') { ret = ret * 10 + ch - '0'; } return ret;}void Read(){ int n, m, p; scanf("%d%d%d", &n, &m, &p); dlx.Init(n * m); getchar(); for (int i = 1; i <= p; ++i) { int x1 = ReadInt(); int y1 = ReadInt(); int x2 = ReadInt(); int y2 = ReadInt(); for (int j = y1 + 1; j <= y2; ++j) { for (int k = x1 + 1; k <= x2; ++k) { dlx.Link(i, (j - 1) * n + k); } } }}int main(){ int T; scanf("%d", &T); while (T--) { Read(); dlx.Solve(); } return 0;}