Simulate a Growing Snake on a Grid and Report the Score After Every Move

A snake moves on a rectangular board with height rows and width columns. Cells are written (row, col), with (0, 0) in the top-left corner. The snake starts as a single segment on (0, 0) with a score of 0.

Food appears one piece at a time, in the order listed in food. Only the first uneaten piece is on the board; as soon as it is eaten, the next piece in the list appears. After the last piece is eaten, no more food appears.

You are given the whole sequence of moves in advance. Simulate the game and return the score after each move, or -1 for the move that ends the game and for every move after it.

Function Signature

def snake_scores(width: int, height: int, food: list[list[int]], moves: str) -> list[int]:

Rules

Each character of moves moves the head one cell: 'U' decreases the row, 'D' increases the row, 'L' decreases the column and 'R' increases the column. Every other segment follows the one ahead of it. For each move, apply these steps in order:

1. Find the cell the head moves into. If it is outside the board, the game ends.
2. If that cell holds the piece of food currently on the board, the snake eats it: the score increases by 1, the tail stays where it is (so the snake becomes one segment longer), and the next piece of food, if any, appears.
3. Otherwise the tail segment leaves its cell, and the snake keeps its length.
4. If the cell the head moves into is occupied by any segment still on the board after step 2 or step 3, the snake has run into itself and the game ends.
5. Otherwise the head occupies the new cell and the move succeeds.

These consequences of the steps are part of the specification:

• Moving into the cell the tail leaves during the same move is legal at any length, including a two-segment snake reversing direction.
• Moving into the tail's cell on a move that eats food ends the game, because the tail does not move on that step.
• Food is eaten only when the head moves onto its cell. A piece that appears on a cell the snake already covers, including the head's own cell, stays there until the head later moves onto that cell.

Output:

• Return a list of exactly len(moves) integers.
• Entry i is the score after move i if that move succeeds, or -1 if move i ends the game.
• Every move after the game has ended also yields -1.

Constraints

• 1 <= width <= 10^4 and 1 <= height <= 10^4
• 0 <= len(food) <= 10^4
• Each food[i] = [r, c] satisfies 0 <= r < height and 0 <= c < width; positions may repeat.
• 1 <= len(moves) <= 10^4, and every character of moves is one of U, D, L, R.
• A score never exceeds len(food), so every output value fits in a 32-bit signed integer.

Examples

Example 1

Input: width = 4, height = 3, food = [[0, 2], [1, 2], [1, 1]], moves = "RRDLUL" Output: [0, 1, 2, 3, 3, 3]

Explanation: the first move only travels. Each of the next three moves lands on the current piece of food, so the snake grows to four segments covering (1, 1), (1, 2), (0, 2) and (0, 1), head first. The fifth move, U, enters (0, 1), which the tail leaves on that same move, so it is legal. The sixth move reaches (0, 0) without incident.

Example 2

Input: width = 3, height = 3, food = [[0, 1], [0, 2], [1, 2], [1, 1]], moves = "RRDLUL" Output: [1, 2, 3, 4, -1, -1]

Explanation: the first four moves eat all four pieces, leaving a five-segment snake on (1, 1), (1, 2), (0, 2), (0, 1) and (0, 0), head first. Moving U sends the head to (0, 1); only the tail on (0, 0) leaves, so (0, 1) is still occupied and the game ends. The final move also yields -1.

Example 3

Input: width = 2, height = 2, food = [[1, 1]], moves = "DRDU" Output: [0, 1, -1, -1]

Explanation: after the snake eats the only piece at (1, 1), moving D would put the head in row 2, which is outside the board.