202. Design Snake Game With Food And Score

Design Snake Game With Food And Score

Design a Snake game played on a rectangular screen.

The screen has size width x height, where width is the number of columns and height is the number of rows.

The snake starts at the top-left cell (0,0) with length 1.

You are given a list of food positions in row-column order. Each food position is represented as "row,column".

Food appears on the board one item at a time. The next food does not appear until the current food has been eaten by the snake.

The snake eats food when its head moves into the cell containing the current food.

When the snake eats food, both the snake length and the game score increase by 1.

When food appears, it is guaranteed that the food is not placed on a cell currently occupied by the snake.

The snake moves one cell at a time in one of four directions: up, down, left, or right.

If the snake moves outside the screen or collides with its own body, the game is over and the move must return -1.

Once the game is over, every later call to move must also return -1.

Class Definition

Implement the class SnakeGame.

Constructor

SnakeGame(int width, int height, List<String> food)

Initializes the game board, the snake, and the ordered list of food positions.

Each string in food is formatted as "row,column".

Method Signature

int move(String direction)

Moves the snake one cell in the given direction.

The direction is one of:

"U": move up by one row
"D": move down by one row
"L": move left by one column
"R": move right by one column

Returns the current score after the move.

If the move causes the snake to hit the border or collide with itself, returns -1.

Movement Rules

The snake's head moves first into the next cell.
If the next cell contains the current food, the snake eats that food and grows by one unit.
If the snake eats food, the tail does not move on that move.
If the snake does not eat food, its tail moves away from its current tail cell.
Moving into the cell that is currently the snake's tail is allowed only when the snake is not eating food on that move, because the tail moves away at the same time.
If the snake eats food, the next food appears immediately after that move, if any food remains.

Return Values

Return the updated score if the game continues.
Return -1 if the snake hits the border.
Return -1 if the snake collides with its own body.
Return -1 for every move after the game has already ended.

Constraints

1 ≤ width ≤ 10,000
1 ≤ height ≤ 10,000
0 ≤ food.size() ≤ 10,000
Each food string is formatted as "row,column".
0 ≤ row < height
0 ≤ column < width
Food positions appear in the exact order given in the input list.
When a food item appears, it is not on a cell currently occupied by the snake.
direction is always one of "U", "D", "L", or "R".
At most 10,000 calls will be made to move.
Do not use null as an input parameter value.

Examples

Example 1

Input:
SnakeGame(width = 4, height = 3, food = ["0,2","1,2","1,1"])
move(direction = "R")
move(direction = "R")
move(direction = "D")
move(direction = "L")
move(direction = "L")

Output:
0
1
2
3
3

Explanation:
The snake starts at (0,0).
After moving right once, the score is still 0.
After moving right again, the snake eats food at (0,2), so the score becomes 1.
Then it moves down and eats food at (1,2), so the score becomes 2.
Then it moves left and eats food at (1,1), so the score becomes 3.
The last left move is valid and does not eat food, so the score remains 3.

Example 2

Input:
SnakeGame(width = 3, height = 3, food = ["2,0"])
move(direction = "D")
move(direction = "D")
move(direction = "D")
move(direction = "R")

Output:
0
1
-1
-1

Explanation:
The snake moves down once to (1,0), so the score remains 0.
The snake moves down again and eats the only food at (2,0), so the score becomes 1.
The next down move goes outside the board, so the game ends and returns -1.
Since the game has already ended, the following move also returns -1.

Example 3

Input:
SnakeGame(width = 2, height = 2, food = ["0,1","1,1"])
move(direction = "R")
move(direction = "D")
move(direction = "L")
move(direction = "R")

Output:
1
2
2
-1

Explanation:
The snake first moves right and eats food at (0,1), so the score becomes 1.
Then the snake moves down and eats food at (1,1), so the score becomes 2.
Then the snake moves left to (1,0). This move does not eat food, so the score remains 2.
The next right move goes from (1,0) to (1,1), which is still occupied by the snake's body, so the game ends and returns -1.

Example 4

Input:
SnakeGame(width = 2, height = 2, food = [])
move(direction = "R")
move(direction = "L")
move(direction = "D")

Output:
0
0
0

Explanation:
There is no food, so the snake never grows and the score remains 0.
Moving back into the previous cell is allowed because the snake has length 1 and its tail moves away on every valid move.