Welcome to Subscribe On Youtube
Question
Formatted question description: https://leetcode.ca/all/353.html
Design a Snake game that is played on a device with screen size height x width. Play the game online if you are not familiar with the game.
The snake is initially positioned at the top left corner (0, 0) with a length of 1 unit.
You are given an array food where food[i] = (ri, ci) is the row and column position of a piece of food that the snake can eat. When a snake eats a piece of food, its length and the game's score both increase by 1.
Each piece of food appears one by one on the screen, meaning the second piece of food will not appear until the snake eats the first piece of food.
When a piece of food appears on the screen, it is guaranteed that it will not appear on a block occupied by the snake.
The game is over if the snake goes out of bounds (hits a wall) or if its head occupies a space that its body occupies after moving (i.e. a snake of length 4 cannot run into itself).
Implement the SnakeGame class:
SnakeGame(int width, int height, int[][] food)Initializes the object with a screen of sizeheight x widthand the positions of thefood.int move(String direction)Returns the score of the game after applying onedirectionmove by the snake. If the game is over, return-1.
Example 1:
Input
["SnakeGame", "move", "move", "move", "move", "move", "move"]
[[3, 2, [[1, 2], [0, 1]]], ["R"], ["D"], ["R"], ["U"], ["L"], ["U"]]
Output
[null, 0, 0, 1, 1, 2, -1]
Explanation
SnakeGame snakeGame = new SnakeGame(3, 2, [[1, 2], [0, 1]]);
snakeGame.move("R"); // return 0
snakeGame.move("D"); // return 0
snakeGame.move("R"); // return 1, snake eats the first piece of food. The second piece of food appears at (0, 1).
snakeGame.move("U"); // return 1
snakeGame.move("L"); // return 2, snake eats the second food. No more food appears.
snakeGame.move("U"); // return -1, game over because snake collides with border
Constraints:
1 <= width, height <= 1041 <= food.length <= 50food[i].length == 20 <= ri < height0 <= ci < widthdirection.length == 1directionis'U','D','L', or'R'.- At most
104calls will be made tomove.
Algorithm
We need a one-dimensional array to store the position of the snake body.
As the head of the snake moves forward a step, the tail of the snake also moves forward, and the body in the middle is still in its original position. As a result of the movement, the head of the snake changes to a new position, removing the position of the tail.
What needs attention is whether the position of removing the snake tail is before or after detecting the collision with the snake body.
- If it is later, you cannot pass this test case:
[[3,3,[[2,0],[0,0]]],["D"],["D"],["U"]], - If it is before, there is no problem
To detect whether the snake head and the snake body collide, use
count(snake.begin(), snake.end(), head)
Code
-
class SnakeGame { private int m; private int n; private int[][] food; private int score; private int idx; private Deque<Integer> q = new ArrayDeque<>(); private Set<Integer> vis = new HashSet<>(); public SnakeGame(int width, int height, int[][] food) { m = height; n = width; this.food = food; q.offer(0); vis.add(0); } public int move(String direction) { int p = q.peekFirst(); int i = p / n, j = p % n; int x = i, y = j; if ("U".equals(direction)) { --x; } else if ("D".equals(direction)) { ++x; } else if ("L".equals(direction)) { --y; } else { ++y; } if (x < 0 || x >= m || y < 0 || y >= n) { return -1; } if (idx < food.length && x == food[idx][0] && y == food[idx][1]) { ++score; ++idx; } else { int t = q.pollLast(); vis.remove(t); } int cur = f(x, y); if (vis.contains(cur)) { return -1; } q.offerFirst(cur); vis.add(cur); return score; } private int f(int i, int j) { return i * n + j; } } /** * Your SnakeGame object will be instantiated and called as such: * SnakeGame obj = new SnakeGame(width, height, food); * int param_1 = obj.move(direction); */ -
''' - The `SnakeGame` class is initialized with `width`, `height`, and `food`. - The `move` method handles the movement of the snake based on the given direction and updates its position. - It checks for collisions with the wall or the snake itself. - It also checks if the snake has eaten food, in which case it increases the size of the snake and increments the score. - The coordinates and movement logic are handled using tuple manipulation. ''' class SnakeGame: def __init__(self, width, height, food): self.width = width self.height = height self.food = food self.score = 0 self.snake = [(0, 0)] def move(self, direction): head = self.snake[0] tail = self.snake[-1] # Pop the tail, as the snake moves forward self.snake.pop() if direction == 'U': head = (head[0] - 1, head[1]) elif direction == 'L': head = (head[0], head[1] - 1) elif direction == 'R': head = (head[0], head[1] + 1) elif direction == 'D': head = (head[0] + 1, head[1]) # Check if the snake has hit the wall or itself if (head in self.snake or head[0] < 0 or head[0] >= self.height or head[1] < 0 or head[1] >= self.width): return -1 # Insert the new head position self.snake.insert(0, head) # Check if the snake eats food if self.food and head == tuple(self.food[0]): self.food.pop(0) self.snake.append(tail) # Grow the snake self.score += 1 return self.score # Example usage game = SnakeGame(3, 2, [[1, 1], [1, 0]]) print(game.move('R')) # 0 print(game.move('D')) # 1 (eats food) print(game.move('D')) # -1 (hits the wall) ############# class SnakeGame: def __init__(self, width: int, height: int, food: List[List[int]]): self.m = height self.n = width self.food = food self.score = 0 self.idx = 0 self.q = deque([(0, 0)]) self.vis = {(0, 0)} def move(self, direction: str) -> int: i, j = self.q[0] x, y = i, j match direction: case "U": x -= 1 case "D": x += 1 case "L": y -= 1 case "R": y += 1 if x < 0 or x >= self.m or y < 0 or y >= self.n: return -1 if ( self.idx < len(self.food) and x == self.food[self.idx][0] and y == self.food[self.idx][1] ): self.score += 1 self.idx += 1 else: self.vis.remove(self.q.pop()) if (x, y) in self.vis: return -1 self.q.appendleft((x, y)) self.vis.add((x, y)) return self.score # Your SnakeGame object will be instantiated and called as such: # obj = SnakeGame(width, height, food) # param_1 = obj.move(direction) -
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<pair<int, int>> food) { this->width = width; this->height = height; this->food = food; score = 0; snake.push_back({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) { auto head = snake.front(), tail = snake.back(); snake.pop_back(); if (direction == "U") --head.first; else if (direction == "L") --head.second; else if (direction == "R") ++head.second; else if (direction == "D") ++head.first; if (count(snake.begin(), snake.end(), head) || head.first < 0 || head.first >= height || head.second < 0 || head.second >= width) { return -1; } snake.insert(snake.begin(), head); if (!food.empty() && head == food.front()) { food.erase(food.begin()); snake.push_back(tail); ++score; } return score; } private: int width, height, score; vector<pair<int, int>> food, snake; }; /** * Your SnakeGame object will be instantiated and called as such: * SnakeGame* obj = new SnakeGame(width, height, food); * int param_1 = obj->move(direction); */ -
type SnakeGame struct { m int n int food [][]int score int idx int q []int vis map[int]bool } func Constructor(width int, height int, food [][]int) SnakeGame { return SnakeGame{height, width, food, 0, 0, []int{0}, map[int]bool{} } } func (this *SnakeGame) Move(direction string) int { f := func(i, j int) int { return i*this.n + j } p := this.q[0] i, j := p/this.n, p%this.n x, y := i, j if direction == "U" { x-- } else if direction == "D" { x++ } else if direction == "L" { y-- } else { y++ } if x < 0 || x >= this.m || y < 0 || y >= this.n { return -1 } if this.idx < len(this.food) && x == this.food[this.idx][0] && y == this.food[this.idx][1] { this.score++ this.idx++ } else { t := this.q[len(this.q)-1] this.q = this.q[:len(this.q)-1] this.vis[t] = false } cur := f(x, y) if this.vis[cur] { return -1 } this.q = append([]int{cur}, this.q...) this.vis[cur] = true return this.score } /** * Your SnakeGame object will be instantiated and called as such: * obj := Constructor(width, height, food); * param_1 := obj.Move(direction); */ -
class SnakeGame { private m: number; private n: number; private food: number[][]; private score: number; private idx: number; private q: number[]; private vis: Set<number>; constructor(width: number, height: number, food: number[][]) { this.m = height; this.n = width; this.food = food; this.score = 0; this.idx = 0; this.q = [0]; this.vis = new Set([0]); } move(direction: string): number { const p = this.q[0]; const i = Math.floor(p / this.n); const j = p % this.n; let x = i; let y = j; if (direction === 'U') { --x; } else if (direction === 'D') { ++x; } else if (direction === 'L') { --y; } else { ++y; } if (x < 0 || x >= this.m || y < 0 || y >= this.n) { return -1; } if ( this.idx < this.food.length && x === this.food[this.idx][0] && y === this.food[this.idx][1] ) { ++this.score; ++this.idx; } else { const t = this.q.pop()!; this.vis.delete(t); } const cur = x * this.n + y; if (this.vis.has(cur)) { return -1; } this.q.unshift(cur); this.vis.add(cur); return this.score; } } /** * Your SnakeGame object will be instantiated and called as such: * var obj = new SnakeGame(width, height, food) * var param_1 = obj.move(direction) */