SRM 525 Medium DropCoins

問題

各セルにコインが乗ってある.上下左右に全体のコインを移動させることが出来る.範囲外にコインをいくつか落としてK個にするまでにかかる最小手数を答えよ.

解答

移動させる時は全体のコインが移動する.その作業をして残ったコインとは,板状のある範囲のコインとなる.なので全ての範囲を考え,中にあるコインがK個かを判定し,その範囲を得るための手数を考えれば良い.

class DropCoins
{
public:
  int getMinimum(vector <string> board, int K)
    {
      int i1, i2, j1, j2, i3, j3;
      int n = board.size();
      int m = board[0].size();
      int res = INT_MAX;
      for(i1 = 0; i1 < n; i1++){
        for(i2 = i1; i2 < n; i2++){
          for(j1 = 0; j1 < m; j1++){
            for(j2 = j1; j2 < m; j2++){
              int count = 0;
              for(i3 = i1; i3 <= i2; i3++){
                for(j3 = j1; j3 <= j2; j3++) if (board[i3][j3] == 'o') count++;
              }
              if (count == K){
                res = min(res,
                          2*min(i1, n-i2-1) + max(i1, n-i2-1)
                          + 2*min(j1, m-j2-1) + max(j1, m-j2-1) );
              }
            }
          }
        }
      }
      if (res == INT_MAX) return -1;
      return res;
    }
};