C++ 150ms, nothing special, just a LIST


  • 0
    Y

    I feel surprised there are so many fancy solutions (dequeue, hashset...etc). It turns out a simple list solution can get really good performance.

    Idea is straightforward, the snake is segmented to separate body and it is saved in a list. When the snake moves, I either increase the first body length or create a new head and then remove the tail if need (if the move doesn't hit the food).

    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]. */
        struct body {
            pair<int, int> latest;
            string direction;
            int length;
            body(pair<int, int> latestIn, string directionIn, int lengthIn):latest(latestIn), direction(directionIn), length(lengthIn) {};
        };
        
        int w, h;
        vector<pair<int, int>> f;
        int fIdx;
        list<body> snake;
        int score;
        SnakeGame(int width, int height, vector<pair<int, int>> food) {
            w = width;
            h = height;
            f = food;
            fIdx = 0;
            score = 0;
            snake.push_back(body(make_pair(0, 0), "R", 1));
        }
        
        /** 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. */
        
        pair<int, int> goNext(pair<int, int> now, string direction) {
            if (direction == "L") 
                return make_pair(now.first, now.second - 1);
            else if (direction == "R")
                return make_pair(now.first, now.second + 1);
            else if (direction == "U")
                return make_pair(now.first - 1, now.second);
            else if (direction == "D")
                return make_pair(now.first + 1, now.second);
            
            
            return make_pair(-1, -1); // error
        }
        
        int move(string direction) {
            pair<int, int> next = goNext(snake.begin()->latest, direction);
            // 3. remove the tail if need
            auto tail = snake.rbegin();
            if (fIdx < f.size() && f[fIdx] == next) { // has a food, no need to remove tail
                score ++;
                fIdx ++;
            } else {
                if (tail->length == 1) snake.pop_back();
                else tail->length --;
            }
            
            // 1. determine if snake is going to colide with its body        
            if (next.first < 0 || next.first >= h || next.second < 0 || next.second >= w) return -1; // colide with the border
            for (auto it = snake.begin(); it != snake.end(); it ++) {
                if (it->latest.first == next.first) { // same row -> check if direction of body is R or L
                    if (it->direction == "L") {
                        if (next.second >= it->latest.second && next.second < it->latest.second + it->length) return -1;
                    } else if (it->direction == "R") {
                        if (next.second <= it->latest.second && next.second > it->latest.second - it->length) return -1;
                    }
                }
                
                if (it->latest.second == next.second) {
                    if (it->direction == "U") {
                        if (next.first >= it->latest.first && next.first < it->latest.first + it->length) return -1;
                    } else if (it->direction == "D") {
                        if (next.first <= it->latest.first && next.first > it->latest.first - it->length) return -1;
                    }
                }
            }
            
            // 2. add new head
            auto head = snake.begin();
            if (head != snake.end() && head->direction == direction) { // just stretch the head
                head->latest = next;
                head->length ++;
            } else { // need to add a new body
                snake.insert(snake.begin(), body(next, direction, 1));
            }
            
            return score;
        }
    };
    
    /**
     * Your SnakeGame object will be instantiated and called as such:
     * SnakeGame obj = new SnakeGame(width, height, food);
     * int param_1 = obj.move(direction);
     */
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.