Topcoder SRM 525 Div1 300

題意：給一個n*m的矩形，每個方格要不為空，要不有金幣，每次你可以將矩形所有金幣選擇一個方向（上下左右）移動一格，如果移動後有金幣出矩形了，則該金幣消失。問最少步驟使得方格金幣恰好為K
(1≤n,m≤30)

解法：枚舉每個子矩形，如果該子矩形含有金幣數量恰好為K，則貪心算出得到該子矩形的代價，即上下移動算一次代價，左右移動算一次代價，兩次代價都分別等於 移動次數最小值*2＋移動次數最大值

Code

#include
#include
#include
#include
#include
#include
#include
using namespace std;
typedef long long ll;

class DropCoins{
public:
    int a[50][50];
    int getMinimum(vector b, int k){
        memset(a,0,sizeof(a));
        for(int i = 0; i < b.size(); i++){
            int t = 0;
            for(int j = 0; j < b[0].length(); j++){
                if(b[i][j] == 'o') ++t;
                a[i][j] = t;
                if(i > 0) a[i][j] += a[i-1][j];
            }
        }
        int ans = 1e9;
        for(int i1 = 0; i1 < b.size(); i1++){
            for(int j1 = 0; j1 < b[0].length(); j1++){
                for(int i2 = i1; i2 < b.size(); i2++){
                    for(int j2 = j1; j2 < b[0].length(); j2++){
                        int a1 = a[i2][j2];
                        if(i1 > 0) a1 -= a[i1-1][j2];
                        if(j1 > 0) a1 -= a[i2][j1-1];
                        if(i1 > 0 && j1 > 0) a1 += a[i1-1][j1-1];
                        if(a1 == k)
                        {
                            int t1, t2, anst = 0;
                            t1 = i1, t2 = (int)b.size() - i2 - 1;
                            anst += 2 * min(t1, t2) + max(t1, t2);

                            t1 = j1, t2 = (int)b[0].length() - j2 - 1;
                            anst += 2 * min(t1, t2) + max(t1, t2);

                            ans = min(ans, anst);
                        }
                    }
                }
            }
        }
        if(ans == 1e9) ans = -1;
        return ans;
    }
};