POJ 1020 紀念日蛋糕：DFS 剪枝與狀態壓縮的靈活應用

題目大意

給定目標正方形邊長 box_size 和 n 個小正方形邊長，判斷能否用這 n 個小正方形無重疊、無空隙地填滿大正方形。小正方形邊長範圍 1~10，數量有限。

核心難點與 DFS 策略

傳統 DFS 按「第 i 塊拼圖放哪」搜索，分支極大。本題關鍵創新：按「下一個待填位置」搜索，即始終找當前最高度最小、最左的空位，嘗試放入可用的大小拼圖。

狀態表示

• col[i]：第 i 列已填充的高度（1-based，寬度為 box_size）
• size_num[s]：邊長為 s 的小正方形剩餘數量

搜索順序優化

1. 找當前 min(col[1..box_size]) 及其最左位置 col_index
2. 從大到小嘗試邊長 size = 10..1（大塊優先，剪枝更強）
3. 檢查放入合法性：
   • 高度不超限：box_size - col[col_index] >= size
   • 寬度不超限：box_size - col_index + 1 >= size
   • 底部平整：col[col_index .. col_index+size-1] 全等於 col[col_index]
4. 放入 → 更新 col[]、size_num[] → 遞歸 → 回溯恢復

關鍵剪枝條件

// 1. 面積不匹配直接返回
if (total_area != box_size * box_size) return false;

// 2. 邊長 > box_size/2 的大塊最多只能有 1 個
//    因為兩塊這樣的大塊無法並排放入
int cnt_big = 0;
for (int s = box_size/2 + 1; s <= 10; ++s)
    cnt_big += size_num[s];
if (cnt_big > 1) return false;

完整代碼

#include <bits/stdc++.h>
using namespace std;

int box_size, n;
int size_num[11], col[65];

bool dfs(int placed) {
    if (placed == n) return true;

    // 找最高度最小、最左的列
    int min_h = INT_MAX, idx = -1;
    for (int i = 1; i <= box_size; ++i)
        if (col[i] < min_h) min_h = col[i], idx = i;

    // 嘗試放入大到小的正方形
    for (int sz = 10; sz >= 1; --sz) {
        if (!size_num[sz]) continue;
        if (box_size - min_h < sz) continue;      // 高度不夠
        if (box_size - idx + 1 < sz) continue;    // 寬度不夠

        // 檢查底部是否平整
        bool flat = true;
        for (int c = idx; c < idx + sz; ++c)
            if (col[c] != min_h) { flat = false; break; }
        if (!flat) continue;

        // 放入
        size_num[sz]--;
        for (int c = idx; c < idx + sz; ++c) col[c] += sz;

        if (dfs(placed + 1)) return true;

        // 回溯
        size_num[sz]++;
        for (int c = idx; c < idx + sz; ++c) col[c] -= sz;
    }
    return false;
}

int main() {
    int cases;
    scanf("%d", &cases);
    while (cases--) {
        memset(size_num, 0, sizeof(size_num));
        memset(col, 0, sizeof(col));
        scanf("%d%d", &box_size, &n);

        int area = 0, big = 0;
        for (int i = 0, s; i < n; ++i) {
            scanf("%d", &s);
            ++size_num[s];
            area += s * s;
            if (s > box_size / 2) ++big;
        }

        if (big > 1 || area != box_size * box_size) {
            puts("HUTUTU!");
            continue;
        }

        puts(dfs(0) ? "KHOOOOB!" : "HUTUTU!");
    }
    return 0;
}

複雜度分析

• 最壞情況指數級，但強剪枝使實際運行極快
• 狀態空間：col[] 共 box_size 列，高度 ≤ box_size
• 搜索深度：n ≤ 64（實際受面積限制更小）

靈感總結

本題展示了 DFS 中「以位置驅動選擇」優於「以塊驅動位置」的思想：固定填充順序（永遠填最低處），將幾何排版問題轉化為有序決策序列，配合大塊優先、平整度檢查等領域知識剪枝，是解決精確覆蓋問題的經典範式。