["SnakeGame", "move", "move", "move", "move", "move", "move"]
[[3, 2, [[1, 2], [0, 1]]], ["R"], ["D"], ["R"], ["U"], ["L"], ["U"]]

[null, 0, 0, 1, 1, 2, -1]

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

class SnakeGame {
private:
    // Grid
    // 0: empty space
    // 1: snake
    // 2: food
    int width, height, score;
    vector<vector<int>> grid;
    deque<pair<int, int>> snakeDeque; // Deque to hold snake segments (head is front)
    queue<pair<int, int>> foodQueue;  // Queue to hold food positions

public:
    // Constructor to initialize the game with given width, height, and food positions
    SnakeGame(int width, int height, vector<vector<int>>& food) {
        this->width = width;
        this->height = height;
        score = 0;
        grid.resize(height, vector<int>(width, 0)); // Initialize grid with all zeros

        // Load the initial food positions into the queue
        for (vector<int>& f : food) {
            foodQueue.push({f[0], f[1]});
        }

        // Place the initial part of the snake on the grid
        grid[0][0] = 1;
        snakeDeque.push_front({0, 0});

        // Place the first piece of food on the grid
        if (!foodQueue.empty()) {
            auto f = foodQueue.front();
            foodQueue.pop();
            grid[f.first][f.second] = 2;
        }
    }
    
    // Method to move the snake in a given direction
    int move(string direction) {
        // Calculate the next position based on the current direction
        auto currentPosition = snakeDeque.front();
        auto nextPosition = currentPosition;

        if (direction == "U") {
            nextPosition.first--;
        } else if (direction == "D") {
            nextPosition.first++;
        } else if (direction == "L") {
            nextPosition.second--;
        } else {
            nextPosition.second++;
        }

        // Check for wall collisions
        if (nextPosition.first < 0 || nextPosition.first >= height ||
            nextPosition.second < 0 || nextPosition.second >= width) {
            return -1; // Game over
        }

        // Determine if the snake has found food
        bool foundFood = (grid[nextPosition.first][nextPosition.second] == 2);

        // If no food is found, snake moves forward: remove tail segment
        if (!foundFood) {
            auto tail = snakeDeque.back();
            grid[tail.first][tail.second] = 0;
            snakeDeque.pop_back();
        }

        // Check for self-collision
        if (grid[nextPosition.first][nextPosition.second] == 1) {
            return -1; // Game over
        }

        // Place new head position on the grid
        snakeDeque.push_front(nextPosition);
        grid[nextPosition.first][nextPosition.second] = 1;

        // If food was found, increase score and place new food if available
        if (foundFood) {
            score++;
            if (!foodQueue.empty()) {
                auto newFoodPosition = foodQueue.front();
                foodQueue.pop();
                grid[newFoodPosition.first][newFoodPosition.second] = 2;
            }
        }

        return score; // Return current score
    }
};

from collections import deque
from queue import Queue

class SnakeGame:
    # Constructor to initialize the game with given width, height, and food positions
    def __init__(self, width, height, food):
        self.width = width
        self.height = height
        self.score = 0
        self.grid = [[0] * width for _ in range(height)]  # Initialize grid with all zeros

        # Load the initial food positions into the queue
        self.foodQueue = Queue()
        for f in food:
            self.foodQueue.put((f[0], f[1]))

        # Place the initial part of the snake on the grid
        self.grid[0][0] = 1
        self.snakeDeque = deque([(0, 0)])

        # Place the first piece of food on the grid
        if not self.foodQueue.empty():
            f = self.foodQueue.get()
            self.grid[f[0]][f[1]] = 2

    # Method to move the snake in a given direction
    def move(self, direction):
        # Calculate the next position based on the current direction
        currentPosition = self.snakeDeque[0]
        nextPosition = list(currentPosition)

        if direction == "U":
            nextPosition[0] -= 1
        elif direction == "D":
            nextPosition[0] += 1
        elif direction == "L":
            nextPosition[1] -= 1
        else:
            nextPosition[1] += 1

        # Check for wall collisions
        if nextPosition[0] < 0 or nextPosition[0] >= self.height or nextPosition[1] < 0 or nextPosition[1] >= self.width:
            return -1  # Game over

        # Determine if the snake has found food
        foundFood = (self.grid[nextPosition[0]][nextPosition[1]] == 2)

        # If no food is found, snake moves forward: remove tail segment
        if not foundFood:
            tail = self.snakeDeque.pop()
            self.grid[tail[0]][tail[1]] = 0

        # Check for self-collision
        if self.grid[nextPosition[0]][nextPosition[1]] == 1:
            return -1  # Game over

        # Place new head position on the grid
        self.snakeDeque.appendleft(tuple(nextPosition))
        self.grid[nextPosition[0]][nextPosition[1]] = 1

        # If food was found, increase score and place new food if available
        if foundFood:
            self.score += 1
            if not self.foodQueue.empty():
                newFoodPosition = self.foodQueue.get()
                self.grid[newFoodPosition[0]][newFoodPosition[1]] = 2

        return self.score  # Return current score