PROBLEM LINKSDIFFICULTYEASY EXPLANATIONFor each cell (r, c) of the grid we can compute the time T[r][c] when the snake makes this cell free. It means that for the next T[r][c]1 moves this cell will be occupied by the snake and at the move T[r][c] tail will leave it (this cell can be immediately occupied by the head but we don't worry about that). For this just simply model the snake movements that given in the input and mark kth cell in this sequence by the number k. (First cell is occupied by the tail and we marked it by 1 and really snake will leave it just in one move. Second cell will be free after two moves and so on). Since N, M <= 1000 we can do this using usual twodimensional array. After that, model the movement of the snake head. If at kth step the head visits the cell (r, c) then it collides with its body if and only if k < T[r][c]. Indeed, if k < T[r][c] then by definition of T[r][c] it means that the snake body still occupies this cell and collision happens otherwise all is fine. So if at some moment we obtain this inequality then we should output "BODY" and k1, otherwise snake will collide with the wall. So the overall complexity is O(M N + L + max{M, N}) per test case (we need to clean corresponding twodimensional array before treatment of the snake movement hence we have M N term, L corresponds to the analyzing of the snake movement and max{M, N} corresponds to the movement of the head.) SETTER'S SOLUTIONCan be found here. TESTER'S SOLUTIONCan be found here.
This question is marked "community wiki".
asked 26 Nov '12, 18:43
