Topcoder SRM 525 Div1 300 DropCoins：枚舉子矩形 + 貪心計算最少移動步數

題目轉化

n×m 網格（n,m ≤ 30），每格有無金幣。每步可將所有金幣向上/下/左/右整體平移一格，移出邊界的金幣消失。求使剩餘金幣數恰好為 K 的最少步數。

關鍵觀察

最終剩餘的金幣必須形成一個子矩形（因為整體平移保持相對位置）。枚舉所有子矩形 (i1,j1)-(i2,j2)，若內部金幣數 == K，計算將該子矩形「推出」邊界所需最少步數。

單向移動代價公式

對於垂直方向：上移 t1 = i1 步可到頂，下移 t2 = n-1-i2 步可到底。最少步數 = 2*min(t1,t2) + max(t1,t2)（來回甩動）。水平同理。總代價 = 垂直代價 + 水平代價。

前綴和加速子矩形金幣計數

int a[50][50]; // 前綴和：a[i][j] 為 (0,0)-(i,j) 金幣數
for(int i=0;i<n;++i) for(int j=0;j<m;++j) {
    a[i][j] = (b[i][j]=='o');
    if(i) a[i][j] += a[i-1][j];
    if(j) a[i][j] += a[i][j-1];
    if(i&&j) a[i][j] -= a[i-1][j-1];
}
// 子矩形 (i1,j1)-(i2,j2) 金幣數：
int cnt = a[i2][j2];
if(i1) cnt -= a[i1-1][j2];
if(j1) cnt -= a[i2][j1-1];
if(i1&&j1) cnt += a[i1-1][j1-1];

完整 AC 代碼

class DropCoins {
public:
    int getMinimum(vector<string> b, int k) {
        int n=b.size(), m=b[0].size();
        int a[50][50]={0};
        for(int i=0;i<n;++i) for(int j=0;j<m;++j) {
            a[i][j] = (b[i][j]=='o');
            if(i) a[i][j] += a[i-1][j];
            if(j) a[i][j] += a[i][j-1];
            if(i&&j) a[i][j] -= a[i-1][j-1];
        }
        int ans = 1e9;
        for(int i1=0;i1<n;++i1) for(int j1=0;j1<m;++j1)
            for(int i2=i1;i2<n;++i2) for(int j2=j1;j2<m;++j2) {
                int cnt = a[i2][j2];
                if(i1) cnt -= a[i1-1][j2];
                if(j1) cnt -= a[i2][j1-1];
                if(i1&&j1) cnt += a[i1-1][j1-1];
                if(cnt == k) {
                    int t1=i1, t2=n-1-i2;
                    int cost = 2*min(t1,t2) + max(t1,t2);
                    t1=j1; t2=m-1-j2;
                    cost += 2*min(t1,t2) + max(t1,t2);
                    ans = min(ans, cost);
                }
            }
        return ans==1e9 ? -1 : ans;
    }
};

複雜度

枚舉子矩形 O(n²m²) = 30⁴ ≈ 8e5，每個 O(1) 查詢，極快通過。