BZOJ 2241 [SDOI2011] 打地鼠：暴力搜尋與剪枝優化完整解析

編輯：關於C語言

BZOJ 2241 [SDOI2011] 打地鼠：暴力搜尋與剪枝優化完整解析

題目大意：給定 m × n 方格，每格初始值 > 0。有一固定大小 x × y 方塊（不可旋轉），每次覆蓋方格中某全非零區域，該區域內每格值減 1。問最少覆蓋幾次可使全方格歸零（保證有 1×1 方塊，必有解）。

核心觀察：枚舉方塊尺寸 + 貪心模擬

方塊尺寸 (x, y) 必須滿足：1 ≤ x ≤ m, 1 ≤ y ≤ n
總和 sum 必須能被 x*y 整除，否則該尺寸不可能
若尺寸固定，覆蓋次數 tans = sum / (x*y) 確定
從左上到右下掃描，遇到非零格必須以該格為左上角放置方塊（貪心策略）

演算法流程


1. 讀入 m, n 及方格值，計算總和 sum
2. 生成所有可能尺寸 (x, y)，按面積 x*y 降序排序（優先嘗試大方塊，答案較小）
3. 遍歷尺寸：
   a. 若 sum % (x*y) != 0 → 略過
   b. tans = sum / (x*y)
   c. 模擬覆蓋過程（work 函數）
   d. 若成功 → 記錄答案並結束（因面積降序，首個成功即最優）
4. 輸出最小覆蓋次數

關鍵函數：work(tx, ty) 模擬驗證

bool work(int tx, int ty) {
    複製原地圖到 tmap
    for i = 1..m
        for j = 1..n
            if tmap[i][j] == 0  continue
            val = tmap[i][j]  // 必須放置 val 次方塊
            for x = 0..tx-1
                for y = 0..ty-1
                    if tmap[i+x][j+y] < val  return false  // 會變負數
                    tmap[i+x][j+y] -= val
    return true
}

剪枝關鍵：面積降序枚舉 + 整除檢查 + 邊界檢查（隱含於陣列大小足夠大）。

完整 C++ 代碼（含註釋）

/************************************************************** 
 Problem: 2241  User: Rainbow6174  Language: C++  Result: Accepted 
 Time:116 ms  Memory:1680 kb 
***************************************************************/
#include <iostream>
#include <algorithm>
#include <cstdio>
using namespace std;

pair<int,int> q[10005];
int n, m, x, sum, ans, flag = 1, tans;
int map[205][205], tmap[205][205];
int tot;

bool work(int tx, int ty) {
    int val, temp, flag;
    for (int i = 1; i <= m; i++)
        for (int j = 1; j <= n; j++)
            tmap[i][j] = map[i][j];

    for (int i = 1; i <= m; i++)
        for (int j = 1; j <= n; j++) {
            if (!tmap[i][j]) continue;
            temp = tmap[i][j];
            for (int x = 0; x < tx; x++)
                for (int y = 0; y < ty; y++)
                    if (tmap[i+x][j+y] - temp < 0) return false;
                    else tmap[i+x][j+y] -= temp;
        }
    return true;
}

bool cmp(pair<int,int> a, pair<int,int> b) {
    return a.first * a.second > b.first * b.second;  // 面積降序
}

void slove() {
    for (int i = 1; i <= m; i++)
        for (int j = 1; j <= n; j++)
            q[tot++] = make_pair(i, j);
    sort(q, q + tot, cmp);

    for (int i = 0; i < tot; i++)
        if (sum % (q[i].first * q[i].second) == 0) {
            tans = sum / (q[i].first * q[i].second);
            if (work(q[i].first, q[i].second)) {
                ans = tans;
                break;
            }
        }
}

int main() {
    scanf("%d%d", &m, &n);
    for (int i = 1; i <= m; i++)
        for (int j = 1; j <= n; j++) {
            scanf("%d", &x);
            if (!x) continue;
            map[i][j] = x;
            sum += x;
        }
    ans = sum;  // 最壞情況：1x1 方塊
    slove();
    printf("%d\n", ans);
    return 0;
}