BZOJ 2241 [SDOI2011] 打地鼠 解題報告：暴力枚舉方塊尺寸

題目大意

給定 m×n 方格，每格初始值 > 0。有一固定大小 x×y 方塊（不可旋轉），每次放置於全非零區域，覆蓋區域內所有值 -1。問最少放置多少次使全盤歸零（保證有 1×1 方塊，必有解）。

關鍵觀察

• 總和 S = Σ map[i][j] 不變
• 每次操作減少 x*y 總量
• 答案 ans = S / (x*y)，故 x*y 必須整除 S
• x ≤ m, y ≤ n，枚舉所有因子對

暴力驗證策略

1. 計算總和 S
2. 枚舉所有可能方塊尺寸 (x,y)，按面積 x*y 從大到小排序（大方塊優先，答案較小）
3. 若 S % (x*y) == 0，模擬驗證是否可行
4. 第一個可行即為最優解

模擬驗證算法

貪心掃描：從左上到右下，遇到非零格 (i,j)，必須放置方塊左上角於此處（否則該格永遠無法歸零）。將方块區域所有值減去 map[i][j]。若過程中出現負值 → 不可行。

bool check(int x, int y) {
    memcpy(tmp, map, sizeof(map));
    for (int i = 1; i <= m; i++) {
        for (int j = 1; j <= n; j++) {
            if (!tmp[i][j]) continue;
            int val = tmp[i][j];
            // 嘗試在 (i,j) 放置 x*y 方塊
            for (int dx = 0; dx < x; dx++) {
                for (int dy = 0; dy < y; dy++) {
                    int nx = i + dx, ny = j + dy;
                    if (nx > m || ny > n) return false; // 越界
                    tmp[nx][ny] -= val;
                    if (tmp[nx][ny] < 0) return false;
                }
            }
        }
    }
    return true;
}

完整程式碼

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

const int MAX = 205;
int m, n, map[MAX][MAX], tmp[MAX][MAX];
vector> candidates;

bool check(int x, int y) {
    for (int i = 1; i <= m; i++)
        for (int j = 1; j <= n; j++)
            tmp[i][j] = map[i][j];

    for (int i = 1; i <= m; i++) {
        for (int j = 1; j <= n; j++) {
            if (!tmp[i][j]) continue;
            int val = tmp[i][j];
            for (int dx = 0; dx < x; dx++) {
                for (int dy = 0; dy < y; dy++) {
                    int nx = i + dx, ny = j + dy;
                    if (nx > m || ny > n) return false;
                    tmp[nx][ny] -= val;
                    if (tmp[nx][ny] < 0) return false;
                }
            }
        }
    }
    return true;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cin >> m >> n;
    long long sum = 0;
    for (int i = 1; i <= m; i++)
        for (int j = 1; j <= n; j++) {
            cin >> map[i][j];
            sum += map[i][j];
        }

    // 枚舉所有可能尺寸
    for (int x = 1; x <= m; x++)
        for (int y = 1; y <= n; y++)
            candidates.emplace_back(x, y);

    // 面積從大到小排序
    sort(candidates.begin(), candidates.end(),
        [](auto &a, auto &b) { return a.first*a.second > b.first*b.second; });

    int ans = sum; // 最壞情況：全用 1x1
    for (auto [x, y] : candidates) {
        int area = x * y;
        if (sum % area != 0) continue;
        if (check(x, y)) {
            ans = sum / area;
            break;
        }
    }
    cout << ans << '\n';
    return 0;
}

複雜度分析

• 候選尺寸：O(m*n) ≤ 40000
• 單次驗證：O(m*n*x*y)，最壞 O((m*n)²)
• 總體：O((m*n)³) 理論上較大，但實際 m,n ≤ 200 且大面積優先快速剪枝，實測極快（~100ms）

優化技巧

1. 面積降序：優先嘗試大方塊，答案小，早停
2. 整除剪枝：sum % area == 0 才驗證
3. 早期終止：驗證過程中出現負值或越界即返回

易錯點

1. 方塊不可旋轉：(x,y) 與 (y,x) 不同，需分別枚舉
2. 邊界檢查：放置時需確保 i+x-1 ≤ m, j+y-1 ≤ n
3. 貪心正確性：掃描順序固定時，最左上非零格必須被當前放置覆蓋，否則無法歸零

總結

本題看似複雜，實為「枚舉因子 + 貪心模擬驗證」。關鍵洞察：

• 總和不變，方塊面積必須整除總和
• 固定掃描順序下，放置位置唯一確定
• 大面積優先枚舉可快速找到最優解

適合 m,n ≤ 200 規模的暴力搜索題。