Build the logic of a snake game. The board has height rows and width columns, and a cell is [row, col] with [0, 0] at the top left. The snake starts with length 1 on [0, 0].
food lists the pieces of food in the order they appear. Only one piece is on the board at a time: at the start it's food[0], and each time a piece is eaten the next one appears. When the list runs out, no more food appears.
Implement the class SnakeGame:
-
SnakeGame(width: int, height: int, food: list[list[int]]) -
move(direction: str) -> int, wheredirectionis"U","D","L"or"R". One move goes like this:- The head steps one cell in that direction. If it leaves the board, the game is over.
- If the head's new cell holds the current piece of food, the snake eats it and grows by one: its tail stays where it is, and the next piece appears. Otherwise the tail moves up, freeing the cell it was on.
- If the head now shares a cell with any other part of the snake, the game is over. (Stepping onto the cell the tail has just freed is fine.)
Return the score (pieces eaten so far), or
-1if the game is over. After the game is over, every latermovereturns-1.
A piece of food may appear under the snake's body. The rules still apply: it is only eaten when the head reaches it.
g = SnakeGame(3, 2, [[1, 2], [0, 1]]) # 3 columns, 2 rows
g.move("R") # 0 head on [0, 1]
g.move("D") # 0 head on [1, 1]
g.move("R") # 1 eats at [1, 2]; the snake is [1, 2], [1, 1] and food appears at [0, 1]
g.move("U") # 1 snake is [0, 2], [1, 2]
g.move("L") # 2 eats at [0, 1]; snake is [0, 1], [0, 2], [1, 2]
g.move("U") # -1 off the board
g.move("D") # -1 the game stays over
Constraints: width * height <= 10^6, up to 10^5 pieces of food and 10^5 calls to move. The snake can grow to tens of thousands of cells, so checking the head against every body cell on each move is too slow. Aim for O(1) per move.
Show hint
You need to add at the head and remove at the tail quickly, and also ask "is this cell part of the snake?" quickly. One structure for each question works well.