Fork me on GitHub

Design Snake Game

Posted on

Description

https://leetcode.com/problems/design-snake-game/description/

Solution

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
class SnakeGame {
private:
    // vector<vector<int>> grid;
    int headX;
    int headY;
    int count;
    int height;
    int width;
    queue<pair<int, int>> que;
    unordered_map<string, pair<int, int>> directions;
    map<pair<int, int>, bool> occupied;
    vector<pair<int, int>> foods;
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) {
        // vector<vector<int>> newGrid(height, vector<int>(width));
        // grid = newGrid;
        directions["R"] = make_pair(0, 1);
        directions["L"] = make_pair(0, -1);
        directions["U"] = make_pair(-1, 0);
        directions["D"] = make_pair(1, 0);
        this->height = height;
        this->width = width;
        headX = 0;
        headY = 0;
        
        que.push(make_pair(headX, headY));
        occupied[make_pair(headX, headY)] = true;
        count = 0;
        foods = food;
    }
    
    /** 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) {
        int newX = headX + directions[direction].first;
        int newY = headY + directions[direction].second;
        
        //Hit the wall
        if (newX < 0 || newX >= height || newY < 0 || newY >= width) return -1;
        
        
        //Pay attention to the order of push and pop, we should try pop(shorten) the snake befroe we push pos into it.
        if (count < foods.size() && newX == foods[count].first && newY == foods[count].second) count += 1;
        else {
            pair<int, int> erase = que.front();
            que.pop();
            occupied.erase(erase);
        }
        
        if (occupied.count(make_pair(newX, newY)) != 0) return -1; //Hit itself
        occupied[make_pair(newX, newY)] = true;
        que.push(make_pair(newX, newY));
        
        headX = newX;
        headY = newY;
        
        return count;
    }
};