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.

class SnakeGame {
    const int dx[4] = {0, 1, 0, -1};
    const int dy[4] = {-1, 0, 1, 0};
    map<string, int> m;
    int score;
    int h;
    int w;
    queue<vector<int>> q;
    list<pair<int,int>> pos;
    set<pair<int,int>> s;
public:
    /** Initialize your data structure here.
        @param width - screen width
        @param height - screen height
        @param food - A list of food positions
        E.g food = [[1,1], [1,0]] means the first food is positioned at [1,1], the second is at [1,0]. */
    SnakeGame(int width, int height, vector<vector<int>>& food) : w(width), h(height), score(0) {
        for(auto& f : food) {
            q.push(f);
        }
        m.insert({"U", 0});
        m.insert({"R", 1});
        m.insert({"D", 2});
        m.insert({"L", 3});
        pos.push_front({0, 0});
        s.insert({0,0});
    }

    /** Moves the snake.
        @param direction - 'U' = Up, 'L' = Left, 'R' = Right, 'D' = Down
        @return The game's score after the move. Return -1 if game over.
        Game over when snake crosses the screen boundary or bites its body. */
    int move(string direction) {
        if(!inRange(pos.front().first, pos.front().second))  return -1;
        pair<int, int> npos = {pos.front().first + dy[m[direction]], pos.front().second + dx[m[direction]]};
        pair<int, int> tail = pos.back();
        pos.pop_back();
        s.erase(tail);
        if(!inRange(npos.first, npos.second))  return -1;
        if(!q.empty() && q.front().front() == npos.first && q.front().back() == npos.second) {
            pos.push_back(tail);
            s.insert(tail);
            q.pop();
            score++;
        }
        pos.push_front(npos);
        if(s.count(npos)) {
            pos.front().first = pos.front().second = -1;
            return -1;
        } else s.insert(npos);

        return score;
    }

    bool inRange(int y, int x) {
        return 0 <= x && x < w && 0 <= y && y < h;
    }
};

/**
 * Your SnakeGame object will be instantiated and called as such:
 * SnakeGame* obj = new SnakeGame(width, height, food);
 * int param_1 = obj->move(direction);
 */