Decent C++ code with explanation


  • 0
    D

    If you go to play this game, you will notice the snake will kill itself if it crosses its body. Then the trick part is how to describe the snake body with what data structure. The game says the snake will grow once it eats food. Let's say the snake is 3 units long now. When the snake moves, the first unit (head) will move as specified in the move function parameter. the second unit will move on to the first unit position, and the third unit will move on to second unit position. Now you can easily figure out queue or deque is good data structure to describe the snake body. I used deque for easy search. Now if the snake crosses its body, it means we can find head in the deque structure. Here is the code.

    class SnakeGame {
        int width, height;
        queue<pair<int, int>> food;
        int row, col;
        int score;
        deque<pair<int, int>> body;    
    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;
            for (auto f : food) this->food.push(f);
            row = 0;
            col = 0;
            score = 0;
            body.push_front(make_pair(row, col));
        }
        
        /** 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) 
        {
            auto tail = body.back(); 
            body.pop_back();
            
            char c = direction[0];
            switch(c)
            {
                case 'U': row--; break;
                case 'D': row++; break;
                case 'L': col--; break;
                case 'R': col++; break;
            }
            if (row < 0 || row >= height || col < 0 || col >= width) return -1;
            
            auto head = make_pair(row, col);
            if (find(body.begin(), body.end(), head) != body.end()) return -1;
            body.push_front(head);
            
            if (row == food.front().first && col == food.front().second)
            {
                food.pop();
                score++;
                body.push_back(tail);
            }
            
            return score;
        }
    };
    

Log in to reply
 

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