Design Snake Game

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.

Example 1

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

Solution Approach

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.

Java

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)