C++ solution, 145ms


  • 0
    S

    Use a queue to store foods, use a vector to store the positions that snake occupied. cur_pos is the snake's head next occupied position. Check this position if it bites itself, or a new food, or just move, or hit the board.

    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) {
            for ( int i = 0; i < food.size(); i++ )
                foods.push(food[i]);
            cur_pos = make_pair(0,0);
            snake.push_back(make_pair(0,0));
            max_depth = height;
            max_length = width;
            num_food = 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) {
            //cout << direction << endl;
            switch (direction[0]) {
                case 'U':
                    cur_pos = make_pair(cur_pos.first-1, cur_pos.second);
                    break;
                case 'L':
                    cur_pos = make_pair(cur_pos.first, cur_pos.second-1);
                    break;
                case 'R':
                    cur_pos = make_pair(cur_pos.first, cur_pos.second+1);
                    break;
                case 'D':
                    cur_pos = make_pair(cur_pos.first+1, cur_pos.second);
                    break;
            }
            if (cur_pos.first < 0 || cur_pos.second < 0 || cur_pos.first >= max_depth || cur_pos.second >= max_length) return -1;
    
            //cout << "cur pos: " << cur_pos.first << " " << cur_pos.second << endl;
            //cout << snake.front().first << " " << snake.front().second << endl;
            for ( int i = 1; i < snake.size(); i++ ) {
                if ( snake[i].first == cur_pos.first && snake[i].second == cur_pos.second ) return -1;
            }
            //cout << "pass" << endl;
            
            if (!foods.empty() && cur_pos.first == foods.front().first && cur_pos.second == foods.front().second) {
                if (foods.empty()) return num_food;
                foods.pop();
                num_food++;
                snake.push_back(cur_pos);
            } else {
                snake.push_back(cur_pos);
                snake.erase(snake.begin());
            }
            //cout << snake.size() << endl;
            return num_food;
        }
    private:
        queue<pair<int,int>> foods;
        vector<pair<int,int>> snake;
    
        pair<int,int> cur_pos;
        int max_depth;
        int max_length;
        int num_food;
    };
    
    

Log in to reply
 

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