SRM 525 div1 easy:DropCoins

問題

TopCoder Statistics - Problem Statement

解法

右端から何列落とすか/左端から何列落とすか/上端から何行落とすか/下端から何行落とすか
で場合分けして全探索します。下のコードは O(h^3 w^3) ですが h, w が十分小さいので間に合います。

const int MAXN = 33;
const int INF = 1e9;

class DropCoins {
public:
    int getMinimum(vector <string> board, int K) {
        int n = board.size();
        int m = board[0].size();
        int ans = INF;
        for (int r = 0; r < m; r++) for (int l = 0; l < m; l++) {
            for (int u = 0; u < n; u++) for (int d = 0; d < n; d++) {
                int cnt = 0;
                for (int i = u; i <= n-1-d; i++) {
                    for (int j = l; j <= m-1-r; j++) {
                        if (board[i][j] == 'o') cnt++;
                    }
                }
                if (cnt == K) {
                    int need = 0;
                    need += l+r+min(l, r);
                    need += d+u+min(d, u);
                    ans = min(ans, need);
                }
            }
        }
        if (ans == INF) ans = -1;
        return ans;
    }
};