SRM550 Div1 Easy(300), Div2 Medium(550) RotatingBot
可能な動きなら、動く範囲は広くない。実際に動かして確かめる。
#include <vector> using namespace std; class RotatingBot{public: int minArea( vector <int> moves ) { int n = (int)moves.size(); int dx[] = { 1, 0, -1, 0 }; int dy[] = { 0, -1, 0, 1 }; // ロボットの動いた範囲を求める int px = 0; int py = 0; int minx = 0; int maxx = 0; int miny = 0; int maxy = 0; for ( int i=0; i<n; i++ ) { px += dx[i%4]*moves[i]; py += dy[i%4]*moves[i]; minx = min(minx,px); maxx = max(maxx,px); miny = min(miny,py); maxy = max(maxy,py); } // 動いた範囲が広すぎたら不可 if ( minx<-100 || 100<maxx || miny<-100 || 100<maxy ) return -1; // チェック int W = maxx-minx+1; int H = maxy-miny+1; vector<vector<bool> > B(H+2,vector<bool>(W+2)); for ( int y=0; y<H+2; y++ ) B[y][0] = B[y][W+1] = true; for ( int x=0; x<W+2; x++ ) B[0][x] = B[H+1][x] = true; px = -minx+1; py = -miny+1; B[py][px] = true; bool ok = true; for ( int i=0; i<n && ok; i++ ) { for ( int j=0; j<moves[i] && ok; j++ ) { px += dx[i%4]; py += dy[i%4]; // 既に訪れたセルなら不可 if ( B[py][px] ) ok = false; B[py][px] = true; } // 最後以外、向きを変えるなら1個前は移動不可のはず if ( i<n-1 && !B[py+dy[i%4]][px+dx[i%4]] ) ok = false; } return ok ? W*H : -1; }};