353. Design Snake Game

After visiting the top rated solutions, I know all we need to do is to maintain a double linked queue. Every move, we get the front node's row index and column index. Then we compute the new front's row and column index. And we also need to pop out the tail node. If the new front node is valid, i.e. it is in the board and also it doesn't hit the snake. Then the question is how to know if it hits the snake? This can be done by hash set. The hash set caches all the nodes' positions. As long as the new node can be found in the hash set, we know it hits the snake itself. Since we have a hash set to keep all the nodes' position, whenever we remove/insert a new node from/into the queue, we need to erase/insert it from/into the hash set too. Note, we need to remove the tail BEFORE checking otherwise the snake is one longer than it should be. If the new node is valid, we push the new node to the front and insert it into hash set. And then we check if the new node hits a food. If so, we increment the score and we push the tail back to the queue back.

When I revisited this problem, I missed line 35. It's important to check the index before accessing an array.

1:  class SnakeGame {  
2:  private:  
3:    int w, h, i;  
4:    deque<pair<int, int>> q;  
5:    vector<pair<int, int>> f;  
6:    set<pair<int, int>> s;  
7:  public:  
8:    /** Initialize your data structure here.  
9:      @param width - screen width  
10:      @param height - screen height   
11:      @param food - A list of food positions  
12:      E.g food = [[1,1], [1,0]] means the first food is positioned at [1,1], the second is at [1,0]. */  
13:    SnakeGame(int width, int height, vector<pair<int, int>> food) {  
14:      w = width, h = height, i = 0;  
15:      f = food;  
16:      q.push_back(make_pair(0, 0));  
17:    }  
18:    /** Moves the snake.  
19:      @param direction - 'U' = Up, 'L' = Left, 'R' = Right, 'D' = Down   
20:      @return The game's score after the move. Return -1 if game over.   
21:      Game over when snake crosses the screen boundary or bites its body. */  
22:    int move(string direction) {  
23:      pair<int, int> head = q.front();  
24:      pair<int, int> tail = q.back();  
25:      int r = head.first, c = head.second;  
26:      q.pop_back();  
27:      s.erase(tail);  
28:      if (direction == "U") r--;  
29:      else if (direction == "D") r++;  
30:      else if (direction == "R") c++;  
31:      else if (direction == "L") c--;  
32:      if (r < 0 || r == h || c < 0 || c == w || s.count(make_pair(r, c))) return -1;  
33:      q.push_front(make_pair(r, c));  
34:      s.insert(make_pair(r, c));  
35:      if (i == f.size()) return q.size()-1;  
36:      if (f[i].first == r && f[i].second == c) {  
37:        q.push_back(tail);  
38:        s.insert(make_pair(tail.first, tail.second));  
39:        i++;  
40:      }  
41:      return q.size()-1;  
42:    }  
43:  };  
44:  /**  
45:   * Your SnakeGame object will be instantiated and called as such:  
46:   * SnakeGame obj = new SnakeGame(width, height, food);  
47:   * int param_1 = obj.move(direction);  
48:   */