Snake Game

Problem

Implement a stripped‑down version of the classic Snake game that runs on a 2D grid. The snake starts in the top‑left cell and grows automatically every five moves – there is no food. Collision logic is the same as the original: the game is over the moment the snake’s head leaves the board or enters a cell already occupied by its body.

Design a class SnakeGame:

SnakeGame(int width, int height)

• Initialises a grid with the supplied width and height.
• The snake sits at position (0, 0) with a starting length of 1.

int move(String direction)

• Moves the snake one step in direction, which is "W" (up), "S" (down), "A" (left) or "D" (right).
• Growth rule – on every 5th move (the 5th, 10th, 15th, …) the snake’s length grows by 1: the head slides into the new cell while the tail stays put.
• On all other moves the snake simply shifts forward – the head advances and the tail pulls forward one cell, keeping the total length unchanged.
• The game ends immediately if the head lands outside the grid or runs into the snake’s own body. In that case the method returns ‑1.
• Otherwise the method returns the snake’s current length after the move.

Constraints

• 1 ≤ width, height ≤ 10⁴
• The snake begins with length 1.
• At most $10^{5}$ calls will be made to move.

Example

Input:

["SnakeGame", "move", "move", "move", "move", "move", "move", "move", "move", "move", "move", "move"]
[[3, 2], ["D"], ["S"], ["D"], ["W"], ["A"], ["A"], ["S"], ["D"], ["D"], ["W"], ["W"]]

Output:

[null, 1, 1, 1, 1, 2, 2, 2, 2, 2, 3, -1]

Explanation:

• SnakeGame game = new SnakeGame(3, 2); – A 3×2 board is created; the snake occupies (0, 0).
• game.move("D"); → returns 1. Head moves right to (0, 1); length remains 1.
• game.move("S"); → returns 1. Head moves down to (1, 1); length remains 1.
• game.move("D"); → returns 1. Head moves right to (1, 2); length remains 1.
• game.move("W"); → returns 1. Head moves up to (0, 2); length remains 1.
• game.move("A"); → returns 2. This is the 5th move: the head shifts left to (0, 1), the tail does not move, so length grows to 2.
• game.move("A"); → returns 2. Head moves left to (0, 0); length remains 2.
• game.move("S"); → returns 2. Head moves down to (1, 0); length remains 2.
• game.move("D"); → returns 2. Head moves right to (1, 1); length remains 2.
• game.move("D"); → returns 2. Head moves right to (1, 2); length remains 2.
• game.move("W"); → returns 3. The 10th move: head goes up to (0, 2) and the tail stays still, so length becomes 3.
• game.move("W"); → returns ‑1. Head moves up to (-1, 2), leaving the grid, so the game terminates.