353. Design Snake Game - cocoder39/coco39_LC GitHub Wiki

353. Design Snake Game

tips:

  • c++ doesn't support non-int switch case
  • c++ doesn't support unordered_set<pair<int, int>>
  • delete tail, insert new head, then check if tail need be restore. To pass test case where new head == tail, this test case won't come from situation snack eats apple since new_head == apple'location != tail (apple would not occupy body)
class SnakeGame {
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<pair<int, int>> food) {
        this->width = width;
        this->height = height;
        foods = food;
        foodIdx = 0;
        score = 0;
        dq.push_back({0, 0});
        st.insert(make_pair(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 (score == -1) {
            return -1;
        }
        
        auto tail= dq.front();
        int row = dq.back().first;
        int col = dq.back().second;
        dq.pop_front();
        st.erase(tail);
        if (direction == "U") {
            row--;
        }
        else if (direction == "D") {
            row++;
        }
        else if (direction == "L") {
            col--;
        }
        else if (direction == "R") {
            col++;
        }
        
        if (row < 0 || row >= height || col < 0 || col >= width || st.find({row, col}) != st.end()) {
            return score = -1;
        }
        
        if (foodIdx < foods.size() && foods[foodIdx] == make_pair(row, col)) {
            foodIdx++;
            score++;
            dq.push_front(tail);
            st.insert(tail); //tail != {row, col} since apple would not occupy body
        }
        dq.push_back({row, col});
        st.insert({row, col});
        return score;
    }
private:
    int width;
    int height;
    vector<pair<int, int>> foods;
    int foodIdx;
    int score;
    deque<pair<int, int>> dq;
    set<pair<int, int>> st;
};

the complexity of std::set::find is O(log n), while std::unordered_set::find is O(1). Serialize pair<int, int>

class SnakeGame {
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<pair<int, int>> food) {
        this->width = width;
        this->height = height;
        foods = food;
        foodIdx = 0;
        score = 0;
        dq.push_back({0, 0});
        st.insert(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 (score == -1) {
            return -1;
        }
        
        int row = dq.back().first;
        int col = dq.back().second;
        auto tail= dq.front();
        int tail_pos = tail.first * width + tail.second;
        dq.pop_front();
        st.erase(tail_pos);
        if (direction == "U") {
            row--;
        }
        else if (direction == "D") {
            row++;
        }
        else if (direction == "L") {
            col--;
        }
        else if (direction == "R") {
            col++;
        }
        
        if (row < 0 || row >= height || col < 0 || col >= width || st.find(row * width + col) != st.end()) {
            return score = -1;
        }
        
        if (foodIdx < foods.size() && foods[foodIdx] == make_pair(row, col)) {
            foodIdx++;
            score++;
            dq.push_front(tail);
            st.insert(tail_pos); //tail != {row, col} since apple would not occupy body
        }
        dq.push_back({row, col});
        st.insert(row * width + col);
        return score;
    }
private:
    int width;
    int height;
    vector<pair<int, int>> foods;
    int foodIdx;
    int score;
    deque<pair<int, int>> dq;
    set<int> st;
};
⚠️ **GitHub.com Fallback** ⚠️