SRM525 Div1 Easy

300
O(N^6)の全通りでも間に合う。



O(N^4)
左上とある点を対角に持つ四角形の中にあるコインの数を、前もって数えておく。

class DropCoins {
public:
  int getMinimum(vector <string> B, int K) 
  {
    const int H = B.size();
    const int W = B[0].size();

    int sum[H + 1][W + 1];
    fill(&sum[0][0], &sum[H][W + 1], 0);
    for (int i = 0; i < H; ++i) {
      for (int j = 0; j < W; ++j) {
        for (int k = 0; k <= i; ++k) {
          for (int l = 0; l <= j; ++l) {
            sum[i + 1][j + 1] += B[k][l] != '.';
          }
        }
      }
    }

    int mn = 1 << 30;
    for (int i = 0; i < H; ++i) {
      for (int j = 0; j < W; ++j) {
        for (int k = i; k < H; ++k) {
          for (int l = j; l < W; ++l) {
            int c = 0;
            c += sum[k + 1][l + 1];
            c += sum[i][j];
            c -= sum[i][l + 1];
            c -= sum[k + 1][j];
            if (c == K) {
              int a = min(i, H - k - 1);
              int b = min(j, W - l - 1);
              mn = min(mn, i + j + H - k - 1 + W - l - 1 + a + b);
            }
          }
        }
      }
    }

    return mn == (1 << 30) ? -1 : mn;
  }

};

本番で通したO(N^6)。全部試す。

class DropCoins {
public:
  int getMinimum(vector <string> B, int K) {

    const int H = B.size();
    const int W = B[0].size();

    char g[H][W];
    for (int i = 0; i < H; ++i) {
      for (int j = 0; j < W; ++j) {
        g[i][j] = B[i][j];
      }
    }

    const int inf = 1 << 30;
    int mn = inf;

    for (int i = 0; i < H; ++i) {
      for (int j = 0; j < W; ++j) {
        for (int k = i; k < H; ++k) {
          for (int l = j; l < W; ++l) {
            int cnt = 0;
            for (int a = i; a <= k; ++a) {
              for (int b = j; b <= l; ++b) {
                if (g[a][b] == 'o') ++cnt;
              }
            }
            cout << i << ' ' << j << " =>> " << k << ' ' << l << endl; 
            if (cnt == K) { 
              int cost = 0;
              int U = i;
              int L = j;
              int D = H - 1 - k;
              int R = W - 1 - l;
              cout << U << ' ' << L << ' ' << D << ' ' << R << endl;
              cost += min(U * 2 + D, D * 2 + U);
              cost += min(R * 2 + L, L * 2 + R);
              mn = min(mn, cost);
            }
          }
        }
      }
    }

    return mn == inf ? -1 : mn;
  }

  

};