SRM550 Div2 Medium

550

やるだけ。シミュレーションする。

const int H = 50 + 2;
const int W = H;

bool vis[H][W];

const int di[] = {0, -1, 0, +1};
const int dj[] = {+1, 0, -1, 0};

bool f(int i, int j, int h, int w, vector<int> M)
{
  fill(&vis[0][0], &vis[H - 1][W], false);
  int dir = 0;
  int ni, nj;

  for (int k = 0; k < M.size(); ++k) {
    while (true) {
      vis[i][j] = true;
      ni = i + di[dir];
      nj = j + dj[dir];
      if (ni < 0 || nj < 0 || h <= ni || w <= nj || vis[ni][nj]) {
        break;
      } else {
        --M[k];
        i = ni;
        j = nj;
      }
    }
    dir = (dir + 1) % 4;
    ni = i + di[dir];
    nj = j + dj[dir];
    if (ni < 0 || nj < 0 || h <= ni || w <= nj || vis[ni][nj]) {
      return M[k] <= 0 && (k + 1) == M.size();
    }
    if (M[k]) {
      return M[k] <= 0 && (k + 1) == M.size();
    }
  }

  return true;
}

class RotatingBot {
public:
  int minArea(vector <int> moves)
  {
    const int inf = 1 << 30;
    int mn = inf;

    for (int h = 1; h < H; ++h) {
      for (int w = 1; w < W; ++w) {
        int j = w - moves[0] - 1;
        if (j < 0) continue;
        for (int i = 0; i < h; ++i) {
          if (f(i, j, h, w, moves)) {
            mn = min(mn, h * w);
          }
        }
      }
    }

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