SRM550 Div1 Easy

300

座標の最大と最小から盤面のサイズを予測する。
予測した盤面上で動きが再現できりるか試す。

問題を把握するまでに時間を要した上に、実装でもつまらない間違いを連発。
悲しい。

class RotatingBot {
public:
  int minArea(vector <int> moves)
  {
    const int di[] = {0, -1, 0, +1};
    const int dj[] = {+1, 0, -1, 0};
    int i = 0;
    int j = 0;
    int dir = 0;

    set< pair<int, int> > vis;
    vis.insert(make_pair(i, j));

    for (int k = 0; k < moves.size(); ++k) {
      for (int step = moves[k]; step--; ) {
        i = i + di[dir];
        j = j + dj[dir];
        pair<int, int> pos = make_pair(i, j);
        if (vis.count(pos)) return -1;
        vis.insert(pos);
      }
      dir = (dir + 1) % 4;
    }

    int mn_i, mx_i;
    int mn_j, mx_j;
    mn_i = mn_j = mx_i = mx_j = 0;
    each (k, vis) {
      mn_i = min(mn_i, k->first);
      mx_i = max(mx_i, k->first);
      mn_j = min(mn_j, k->second);
      mx_j = max(mx_j, k->second);
    }

    vis.clear();
    vis.insert(make_pair(0, 0));
    dir = 0;
    i = j = 0;
    for (int k = 0; k < moves.size() - 1; ++k) {
      for (int step = moves[k]; step--; ) {
        i = i + di[dir];
        j = j + dj[dir];
        vis.insert(make_pair(i, j));
      }
      int ni = i + di[dir];
      int nj = j + dj[dir];
      dir = (dir + 1) % 4;

      bool hata = false;
      hata = hata || (ni < mn_i);
      hata = hata || (nj < mn_j);
      hata = hata || (mx_i < ni);
      hata = hata || (mx_j < nj);
      hata = hata || vis.count(make_pair(ni, nj));
      if (!hata) return -1;
    }

    return (mx_i - mn_i + 1) * (mx_j - mn_j + 1);
  }
};