# 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 71 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>& 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> food; unordered_set lookup; deque 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 76 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 lookup = new HashSet<>(); private Deque 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 = 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