题意：一个 n x m 的矩形(1 <= n, m <= 30)，现给出这个矩形中 p 个（1 <= p <= 500）子矩形的左下角与右下角坐标，问最少用多少个子矩形可以恰好组成这个 n x m 的大矩形。
题目链接：http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemId=3372
——>>这是精确覆盖问题，而DLX正是解决精确覆盖问题的有利武器。。
模型转换：将原矩形变成一行，作为 DLX 中的列，表示要被覆盖一次且仅一次的目标。子矩形则是行中的一些点，每个子矩形作为 DLX 的一行，它所覆盖行中的点的位置标为1，其余位标为0，则问题转化为：选出最少的行，使得选出的行中每一列有且仅有一个1，这正是 DLX 解决的问题。。
注：在往下一层 dfs 的时候，如果检测返回值为真，可别来个return true，这时会中断后面的搜索（很隐秘地 WA 了几发）。。为了方便，我不要返回值了。。
为了加快搜索，可以来个剪枝，dfs 时检测当前深度是否 >= 已搜索到的可满足要求的长度。。
#include <cstdio>
#include <cstring>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;
}