SRM 525 DIV1 250 dropcoins

完敗(^O^)／

どうせ探索問題だろうとおもったのが、すべての敗因でした。このやり方知ってるのに出て来なかったのは悔しい。ばか、もうほんとばか。

int cnt[31][31];
class DropCoins {
public:
    int getMinimum(vector<string> board, int K) {
        int r = board.size();
        int c = board[0].length();

        int ret = INF;
        memset(cnt, 0, sizeof(cnt));
        FOR (i, 1, r+1) FOR (j, 1, c+1) {
            cnt[i][j] = cnt[i-1][j] + cnt[i][j-1] - cnt[i-1][j-1] + (board[i-1][j-1] == 'o');
        }

        FOR (i, 1, r+1) FOR (j, 1, c+1) FOR (it, i, r+1) FOR (jt, j, c+1) {
            int x = cnt[it][jt] + cnt[i-1][j-1] - cnt[it][j-1] - cnt[i-1][jt];

            if (x == K) {
                int ans = (i-1)+(j-1)
                        + (r-it)+(c-jt)
                        + min(i-1, r-it)
                        + min(j-1, c-jt);
                ret = min(ret, ans);
            }
        }

        if (ret == INF) return -1;
        return ret;
    }
};