# 353 Design Snake Game

Design a Snake game that is played on a device with screen size `height x width`. Play the game online if you are not familiar with the game.

The snake is initially positioned at the top left corner `(0, 0)` with a length of `1` unit.

You are given an array `food` where `food[i] = (ri, ci)` is the row and column position of a piece of food that the snake can eat. When a snake eats a piece of food, its length and the game's score both increase by `1`.

Each piece of food appears one by one on the screen, meaning the second piece of food will not appear until the snake eats the first piece of food.

When a piece of food appears on the screen, it is guaranteed that it will not appear on a block occupied by the snake.

The game is over if the snake goes out of bounds (hits a wall) or if its head occupies a space that its body occupies after moving (i.e. a snake of length 4 cannot run into itself).

Implement the `SnakeGame` class:

• `SnakeGame(int width, int height, int[][] food)` Initializes the object with a screen of size `height x width` and the positions of the food.
• `int move(String direction)` Returns the score of the game after applying one `direction` move by the snake. If the game is over, return `-1`.

Example 1:

``````o _ _   =>   _ o _   =>   _ _ _   =>   _ 2 _
_ _ 1   R    _ _ 1   D    _ o 1   R    _ o o

=>   _ 2 o   =>   _ o o   =>   _ x x
U    _ _ o   L    _ _ o   U    _ _ x

Input
["SnakeGame", "move", "move", "move", "move", "move", "move"]
[[3, 2, [[1, 2], [0, 1]]], ["R"], ["D"], ["R"], ["U"], ["L"], ["U"]]
Output
[null, 0, 0, 1, 1, 2, -1]

Explanation
SnakeGame snakeGame = new SnakeGame(3, 2, [[1, 2], [0, 1]]);
snakeGame.move("R"); // return 0
snakeGame.move("D"); // return 0
snakeGame.move("R"); // return 1, snake eats the first piece of food. The second piece of food appears at (0, 1).
snakeGame.move("U"); // return 1
snakeGame.move("L"); // return 2, snake eats the second food. No more food appears.
snakeGame.move("U"); // return -1, game over because snake collides with border
``````

Constraints:

• `1 <= width, height <= 104`
• `1 <= food.length <= 50`
• `food[i].length == 2`
• `0 <= ri < height`
• `0 <= ci < width`
• `direction.length == 1`
• `direction` is `'U'`, `'D'`, `'L'`, or `'R'`.
• At most `104` calls will be made to `move`.
 `````` 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 `````` ``````class SnakeGame: DIR = { 'L': (0, -1), 'R': (0, 1), 'U': (-1, 0), 'D': (1, 0), } def __init__(self, width: int, height: int, food: List[List[int]]): self.w = width self.h = height self.q = deque([(0, 0)]) self.body = set([(0, 0)]) self.foods = deque(food) self.food = self.foods.popleft() def move(self, direction: str) -> int: dr, dc = self.DIR[direction] # delta hr, hc = self.q[-1] # head nr, nc = hr + dr, hc + dc # new_head # check boundaries if nr < 0 or nr >= self.h or nc < 0 or nc >= self.w: return -1 # check collasion if (nr, nc) in self.body and (nr, nc) != self.q[0]: # new_head is in body (without tail) return -1 # check food if [nr, nc] == self.food: self.food = self.foods.popleft() if self.foods else None else: # remove tail self.body.remove(self.q.popleft()) # add new_head self.q.append((nr, nc)) self.body.add((nr, nc)) return len(self.body) - 1 # Your SnakeGame object will be instantiated and called as such: # obj = SnakeGame(width, height, food) # param_1 = obj.move(direction)``````