SRM 550 div1 easy: RotatingBot

問題

TopCoder Statistics - Problem Statement

解法

素直に実装するだけです。

あんまりおもしろくない…

const int SIZE = 1000;
bool done[SIZE][SIZE];

class RotatingBot {
public:
    int minArea(vector <int> moves) {
        int n = moves.size();
        if (n == 1) return moves[0]+1;
        if (n == 2) return (moves[0]+1)*(moves[1]+1);
        if (n == 3) return (max(moves[0], moves[2])+1) * (moves[1]+1);
        int sy = SIZE/2, sx = SIZE/2;
        memset(done, false, sizeof(done));
        done[sy][sx] = true;
        int L = sx, R = sx, U = sy, D = sy;
        int y = sy, x = sx;
        for (int i = 0; i < n; i++) {
            //cout << i << endl;
            int dir = i%4;
            for (int j = 0; j < moves[i]; j++) {
                y += dy[dir], x += dx[dir];
                if (done[y][x]) return -1;
                done[y][x] = true;
            }
            if (i < n-1) {
                int ny = y+dy[dir], nx = x+dx[dir];
                if (i%2 == 0) {
                    if (!done[ny][nx] && L <= nx && nx <= R) return -1;
                } else {
                    if (!done[ny][nx] && U <= ny && ny <= D) return -1;
                }
            }
            if (i >= 4) {
                if (x > R || x < L || y > D || y < U) return -1;
            }
            L = min(L, x);
            R = max(R, x);
            U = min(U, y);
            D = max(D, y);
        }
        return (R-L+1)*(D-U+1);
    }
};