您现在的位置：程式碼之家 >> 編程語言 > >> C語言 >> C++ >> C++ 入門

ZOJ 3209 Dancing Links：精確覆蓋問題的 DLX 算法實戰

編輯：C++ 入門

問題建模：矩形覆蓋轉化為精確覆蓋

給定 n×m 網格和 p 個矩形，每個矩形覆蓋若干格子。選擇最少矩形，使每個格子被恰好覆蓋一次。
這是經典的精確覆蓋問題，Dancing Links (DLX) 是其最高效求解算法。

矩陣構建

列：n×m 個格子（每格必須被覆蓋恰好一次）
行：p 個矩形（每行對應一個矩形覆蓋的格子集合）
矩陣元素：矩形 i 覆蓋格子 j → matrix[i][j] = 1

DLX 核心數據結構：十字雙向鏈表

// 鏈表節點字段
U[maxn], D[maxn], L[maxn], R[maxn]; // 上下左右指針
H[maxn], ROW[maxn], C[maxn], S[maxn]; // 行頭、行號、列號、列大小
O[maxn]; // 解記錄

int head, sz; // 頭節點、節點總數

void init(int m) { // m 列
    head = 0;
    for (int i = 0; i <= m; i++) {
        U[i] = D[i] = i;
        L[i] = i - 1; R[i] = i + 1;
        S[i] = 0;
    }
    R[m] = 0; L[0] = m;
    S[0] = INF; // 頭節點列大小設為無窮大
    sz = m + 1;
    memset(H, 0, sizeof(H));
}

void insert(int row, int col) { // 插入節點 (row, col)
    if (H[row]) { // 行已有節點，插入行尾
        L[sz] = L[H[row]];
        R[sz] = H[row];
        L[R[sz]] = sz;
        R[L[sz]] = sz;
    } else { // 行首節點
        L[sz] = R[sz] = sz;
        H[row] = sz;
    }
    // 列鏈表插入列尾
    U[sz] = U[col];
    D[sz] = col;
    U[D[sz]] = sz;
    D[U[sz]] = sz;
    C[sz] = col;
    ROW[sz] = row;
    S[col]++;
    sz++;
}

核心操作：Cover / Uncover（刪除/恢復列及相關行）

void remove(int c) { // 覆蓋列 c
    L[R[c]] = L[c]; R[L[c]] = R[c]; // 列鏈表中刪除 c
    for (int i = D[c]; i != c; i = D[i]) // 遍歷列 c 的所有行
        for (int j = R[i]; j != i; j = R[j]) { // 遍歷該行的其他列
            U[D[j]] = U[j]; D[U[j]] = D[j]; // 列鏈表中刪除 j
            S[C[j]]--;
        }
}

void resume(int c) { // 恢復列 c（逆序操作）
    for (int i = U[c]; i != c; i = U[i])
        for (int j = L[i]; j != i; j = L[j]) {
            S[C[j]]++;
            U[D[j]] = j; D[U[j]] = j;
        }
    L[R[c]] = c; R[L[c]] = c;
}

DFS 搜索：啟發式選擇最小列

int ans;

void dfs(int k) {
    if (R[head] == head) { // 所有列覆蓋完成
        ans = min(ans, k);
        return;
    }
    // 選擇節點最少的列（啟發式優化）
    int c = R[head], min_s = S[c];
    for (int t = R[head]; t != head; t = R[t])
        if (S[t] < min_s) min_s = S[t], c = t;
    
    remove(c);
    for (int i = D[c]; i != c; i = D[i]) {
        O[k] = ROW[i];
        for (int j = R[i]; j != i; j = R[j]) remove(C[j]);
        dfs(k + 1);
        for (int j = L[i]; j != i; j = L[j]) resume(C[j]);
    }
    resume(c);
}

完整主程序

int main() {
    int T; scanf("%d", &T);
    while (T--) {
        int n, m, p;
        scanf("%d%d%d", &n, &m, &p);
        init(n * m);
        
        for (int i = 1; i <= p; i++) {
            int x1, y1, x2, y2;
            scanf("%d%d%d%d", &x1, &y1, &x2, &y2);
            // 注意：題目座標可能從 0 或 1 開始，格子編號 = x*m + y
            for (int x = x1; x < x2; x++)
                for (int y = y1 + 1; y <= y2; y++)
                    insert(i, x * m + y);
        }
        
        ans = INF;
        dfs(0);
        printf("%d\n", ans == INF ? -1 : ans);
    }
    return 0;
}