PROBLEM LINKS
DIFFICULTY
EASY
EXPLANATION
For 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 k-th 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 two-dimensional array. After that, model the movement of the snake head. If at k-th 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 k-1, 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 two-dimensional 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 SOLUTION
Can be found here.
TESTER’S SOLUTION
Can be found here.