SRM 550 div1 easy: RotatingBot
解法
素直に実装するだけです。
あんまりおもしろくない…
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); } };