LeetCode Solutions

			

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 move(string direction) {
    // Old head's position
    int i = body.front() / width;
    int j = body.front() % width;

    // Update head's position and check if out of bound
    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);

    // Case 1: eat food and increase 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;
    }

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

    // Case 3: normal case
    // Remove old tail first (important), 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;
  }
};

			

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) {
    // Old head's position
    int i = body.peekFirst() / width;
    int j = body.peekFirst() % width;

    // Update head's position and check if out of bound
    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);

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

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

    // Case 3: normal case
    // Remove old tail first (important), 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;
  }
}

			

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 = 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.
    """
    # Old head's position
    i = self.body[0] // self.width
    j = self.body[0] % self.width

    # Update head's position and check if out of bound
    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)

    # Case 1: eat food and increase 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

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

    # Case 3: normal case
    # Remove old tail first(important), 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