SRM 525 DIV1 250 dropcoins

完敗(^O^)／

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

view plainprint?

1. int cnt[31][31];  
2. class DropCoins {  
3. public:  
4.     int getMinimum(vector<string> board, int K) {  
5.         int r = board.size();  
6.         int c = board[0].length();  
7.   
8.         int ret = INF;  
9.         memset(cnt, 0, sizeof(cnt));  
10.         FOR (i, 1, r+1) FOR (j, 1, c+1) {  
11.             cnt[i][j] = cnt[i-1][j] + cnt[i][j-1] - cnt[i-1][j-1] + (board[i-1][j-1] == 'o');  
12.         }  
13.   
14.         FOR (i, 1, r+1) FOR (j, 1, c+1) FOR (it, i, r+1) FOR (jt, j, c+1) {  
15.             int x = cnt[it][jt] + cnt[i-1][j-1] - cnt[it][j-1] - cnt[i-1][jt];  
16.   
17.             if (x == K) {  
18.                 int ans = (i-1)+(j-1)  
19.                         + (r-it)+(c-jt)  
20.                         + min(i-1, r-it)  
21.                         + min(j-1, c-jt);  
22.                 ret = min(ret, ans);  
23.             }  
24.         }  
25.   
26.         if (ret == INF) return -1;  
27.         return ret;  
28.     }  
29. };  

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;
    }
};