Design Snake Game
Difficulty: Medium
Category: DSA
Topics: Array, Hash Table, Design, Queue, Simulation
Asked at: Amazon, Microsoft
You are given the task of designing a **Snake Game** played on a 2D grid with dimensions `width` x `height`. The snake starts at position `(0, 0)` and can move in four directions: `'U'` (up), `'D'` (down), `'L'` (left), and `'R'` (right). The game is initialized with a list of food positions `food`, where `food[i] = [ri, ci]` represents the row and column of the `i`th food item. Food appears on the board in the order given by `food`.
Each time the snake moves, it must move one cell in the specified direction. If the snake's head moves to a cell containing food, the snake eats the food and its length increases by one. Otherwise, the snake moves forward by removing its tail. The game ends if the snake moves out of bounds or runs into itself.
Implement the following methods:
- `SnakeGame(int width, int height, int[][] food)`: Initializes the game with the given grid size and food positions.
- `int move(String direction)`: Moves the snake in the specified direction. Returns the game's score (number of food items eaten) after the move, or returns `-1` if the game is over due to collision or moving out of bounds.
**Constraints:**
- `1 <= width, height <= 10^4`
- `1 <= food.length <= 50`
- `food[i].length == 2`
- `0 <= ri < height`
- `0 <= ci < width`
- `direction` is one of `'U'`, `'D'`, `'L'`, `'R'`
Return the score after each move, or `-1` if the game has ended.