Skip to content

353. Design Snake Game

  • Time:
  • Space: 
 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
67
68
69
70
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<vector<int>>& food)
      : width(width), height(height), food(food) {
    lookup.insert(getId(0, 0));
    body.push_back(getId(0, 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 std::move(string direction) {
    // the old head's position
    int i = body.front() / width;
    int j = body.front() % width;

    // Update the head's position and check if it's out-of-bounds.
    if (direction == "U" && --i < 0)
      return -1;
    if (direction == "L" && --j < 0)
      return -1;
    if (direction == "R" && ++j == width)
      return -1;
    if (direction == "D" && ++i == height)
      return -1;

    const int newHead = getId(i, j);

    // 1. Eat food and increase the size by 1.
    if (k < food.size() && i == food[k][0] && j == food[k][1]) {
      lookup.insert(newHead);
      body.push_front(newHead);
      ++k;
      return ++score;
    }

    // 2. new head != old tail and eat body!
    if (newHead != body.back() && lookup.contains(newHead))
      return -1;

    // 3. normal case
    // Remove the old tail first, then add new head because new head may be in
    // old tail's position.
    lookup.erase(body.back());
    lookup.insert(newHead);
    body.pop_back();
    body.push_front(newHead);
    return score;
  }

 private:
  int width;
  int height;
  int score = 0;
  int k = 0;  // food's index
  vector<vector<int>> food;
  unordered_set<int> lookup;
  deque<int> body;  // snake's body

  int getId(int i, int j) {
    return i * width + j;
  }
};

 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
67
68
69
70
71
72
73
74
75
class SnakeGame {
  /**
   * 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].
   */
  public SnakeGame(int width, int height, int[][] food) {
    this.width = width;
    this.height = height;
    this.food = food;
    lookup.add(getId(0, 0));
    body.offerLast(getId(0, 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.
   */
  public int move(String direction) {
    // the old head's position
    int i = body.peekFirst() / width;
    int j = body.peekFirst() % width;

    // Update the head's position and check if it's out-of-bounds.
    if (direction.equals("U") && --i < 0)
      return -1;
    if (direction.equals("L") && --j < 0)
      return -1;
    if (direction.equals("R") && ++j == width)
      return -1;
    if (direction.equals("D") && ++i == height)
      return -1;

    final int newHead = getId(i, j);

    // 1. Eat food and increase the size by 1.
    if (k < food.length && i == food[k][0] && j == food[k][1]) {
      lookup.add(newHead);
      body.offerFirst(newHead);
      ++k;
      return ++score;
    }

    // 2. new head != old tail and eat body!
    if (newHead != body.peekLast() && lookup.contains(newHead))
      return -1;

    // 3. normal case
    // Remove the old tail first, then add new head because new head may be in
    // old tail's position.
    lookup.remove(body.peekLast());
    lookup.add(newHead);
    body.pollLast();
    body.offerFirst(newHead);
    return score;
  }

  private int width;
  private int height;
  private int score = 0;
  private int k = 0; // food's index
  private int[][] food;
  private Set<Integer> lookup = new HashSet<>();
  private Deque<Integer> body = new ArrayDeque<>(); // snake's body

  private int getId(int i, int j) {
    return i * width + j;
  }
}

 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
67
68
69
70
71
72
class SnakeGame:
  def __init__(self, width: int, height: int, food: list[list[int]]):
    """
    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].
    """
    self.width = width
    self.height = height
    self.food = food
    self.score = 0
    self.k = 0  # food's index
    self.lookup = set([self.getId(0, 0)])
    self.body = collections.deque([self.getId(0, 0)])  # snake's body

  def move(self, direction: str) -> int:
    """
    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.
    """
    # the old head's position
    i = self.body[0] // self.width
    j = self.body[0] % self.width

    # Update the head's position and check if it's out-of-bounds.
    if direction == "U":
      i -= 1
      if i < 0:
        return -1
    if direction == "L":
      j -= 1
      if j < 0:
        return -1
    if direction == "R":
      j += 1
      if j == self.width:
        return -1
    if direction == "D":
      i += 1
      if i == self.height:
        return -1

    newHead = self.getId(i, j)

    # 1. Eat food and increase the size by 1.
    if self.k < len(self.food) and i == self.food[self.k][0] and j == self.food[self.k][1]:
      self.lookup.add(newHead)
      self.body.appendleft(newHead)
      self.k += 1
      self.score += 1
      return self.score

    # 2. new head != old tail and eat body!
    if newHead != self.body[-1] and newHead in self.lookup:
      return -1

    # 3. normal case
    # Remove the old tail first, then add new head because new head may be in
    # old tail's position.
    self.lookup.remove(self.body[-1])
    self.lookup.add(newHead)
    self.body.pop()
    self.body.appendleft(newHead)

    return self.score

  def getId(self, i: int, j: int) -> int:
    return i * self.width + j