Design a snake game that is played on a m x n screen. The snake moves one step at a time and can eat food to grow. Return the score or -1 if game over.
SnakeGame(3,2,[[1,2],[0,1]]), move("R")→0, move("D")→0, move("R")→1, move("U")→1, move("L")→2, move("U")→-1
Use a Deque for the snake body. On each move, add new head position and remove tail (unless food is eaten). Check for wall or self-collision.
- Deque snake (stores {row,col}). Set body for O(1) collision check.
- On move: compute new head. Check wall bounds.
- Check if body contains new head.
- If food available and head == food: score++, advance food index; else remove tail.
- Add new head to both deque and set.
import java.util.*;
class SnakeGame {
int m, n, foodIdx=0, score=0;
int[][] food;
Deque<int[]> snake = new ArrayDeque<>();
Set<Integer> body = new HashSet<>();
Map<String,int[]> dirMap;
public SnakeGame(int width, int height, int[][] food) {
n=width; m=height; this.food=food;
snake.addFirst(new int[]{0,0}); body.add(0);
dirMap = Map.of("U",new int[]{-1,0},"D",new int[]{1,0},"L",new int[]{0,-1},"R",new int[]{0,1});
}
public int move(String direction) {
int[] d = dirMap.get(direction);
int[] head = snake.peekFirst();
int nr = head[0]+d[0], nc = head[1]+d[1];
if (nr<0||nr>=m||nc<0||nc>=n) return -1;
int[] tail = snake.peekLast();
body.remove(tail[0]*n+tail[1]); // tentatively remove tail
if (body.contains(nr*n+nc)) return -1;
if (foodIdx < food.length && food[foodIdx][0]==nr && food[foodIdx][1]==nc) {
score++; foodIdx++;
body.add(tail[0]*n+tail[1]); // restore tail (snake grows)
} else {
snake.removeLast();
}
snake.addFirst(new int[]{nr,nc}); body.add(nr*n+nc);
return score;
}
}
- Time Complexity: move: O(1)
- Space Complexity: O(M*N)