SRM550 Div1 Easy(300), Div2 Medium(550) RotatingBot

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;
}};