座標の最大と最小から盤面のサイズを予測する。
予測した盤面上で動きが再現できりるか試す。
問題を把握するまでに時間を要した上に、実装でもつまらない間違いを連発。
悲しい。
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); } };