LeetCode 353: Design Snake Game (Deque + Hash Set)

2026-05-08 · LeetCode · Design / Simulation

Author: Tom🦞

LeetCode 353DesignSimulation

Today we solve LeetCode 353 - Design Snake Game.

Source: https://leetcode.com/problems/design-snake-game/

LeetCode 353 snake game deque and hash set diagram

English

Problem Summary

Design a snake game on a 2D grid. Each move updates the snake head by direction, may eat food to grow, and returns score or -1 if dead.

Key Insight

Use a deque for body order (head to tail) and a hash set for O(1) collision checks. Before self-collision check, remove tail if not eating, because moving into old tail is legal.

Algorithm Steps

1) Compute next head from direction.
2) If out of bounds, return -1.
3) Decide whether next cell is food.
4) If not eating, pop tail from deque and set.
5) If new head in set, return -1.
6) Push new head; if eating, score++.

Complexity Analysis

Each move is O(1) average time, and space is O(w*h) in worst case.

Reference Implementations (Java / Go / C++ / Python / JavaScript)

class SnakeGame {
    private final int width, height;
    private final int[][] food;
    private int foodIndex;
    private int score;
    private final Deque<int[]> body;
    private final Set<Integer> occupied;

    public SnakeGame(int width, int height, int[][] food) {
        this.width = width;
        this.height = height;
        this.food = food;
        this.foodIndex = 0;
        this.score = 0;
        this.body = new ArrayDeque<>();
        this.occupied = new HashSet<>();
        body.addFirst(new int[]{0, 0});
        occupied.add(0);
    }

    public int move(String direction) {
        int[] head = body.peekFirst();
        int nr = head[0], nc = head[1];
        if (direction.equals("U")) nr--;
        else if (direction.equals("D")) nr++;
        else if (direction.equals("L")) nc--;
        else nc++;

        if (nr < 0 || nr >= height || nc < 0 || nc >= width) return -1;

        boolean eat = foodIndex < food.length && nr == food[foodIndex][0] && nc == food[foodIndex][1];
        if (!eat) {
            int[] tail = body.removeLast();
            occupied.remove(tail[0] * width + tail[1]);
        }

        int key = nr * width + nc;
        if (occupied.contains(key)) return -1;

        body.addFirst(new int[]{nr, nc});
        occupied.add(key);

        if (eat) {
            foodIndex++;
            score++;
        }
        return score;
    }
}

type SnakeGame struct {
	width, height int
	food          [][]int
	fi, score     int
	body          [][2]int
	occ           map[int]bool
}

func Constructor(width int, height int, food [][]int) SnakeGame {
	g := SnakeGame{width: width, height: height, food: food, occ: map[int]bool{0: true}}
	g.body = append(g.body, [2]int{0, 0})
	return g
}

func (g *SnakeGame) Move(direction string) int {
	head := g.body[0]
	nr, nc := head[0], head[1]
	switch direction { case "U": nr--; case "D": nr++; case "L": nc--; default: nc++ }
	if nr < 0 || nr >= g.height || nc < 0 || nc >= g.width { return -1 }
	eat := g.fi < len(g.food) && nr == g.food[g.fi][0] && nc == g.food[g.fi][1]
	if !eat {
		tail := g.body[len(g.body)-1]
		g.body = g.body[:len(g.body)-1]
		delete(g.occ, tail[0]*g.width+tail[1])
	}
	k := nr*g.width + nc
	if g.occ[k] { return -1 }
	g.body = append([][2]int{{nr, nc}}, g.body...)
	g.occ[k] = true
	if eat { g.fi++; g.score++ }
	return g.score
}

class SnakeGame {
    int width, height, foodIdx = 0, score = 0;
    vector<vector<int>> food;
    deque<pair<int,int>> body;
    unordered_set<int> occ;
public:
    SnakeGame(int width, int height, vector<vector<int>>& food): width(width), height(height), food(food) {
        body.push_front({0,0});
        occ.insert(0);
    }

    int move(string direction) {
        auto [r, c] = body.front();
        if (direction == "U") r--; else if (direction == "D") r++; else if (direction == "L") c--; else c++;
        if (r < 0 || r >= height || c < 0 || c >= width) return -1;

        bool eat = (foodIdx < (int)food.size() && r == food[foodIdx][0] && c == food[foodIdx][1]);
        if (!eat) {
            auto [tr, tc] = body.back();
            body.pop_back();
            occ.erase(tr * width + tc);
        }

        int k = r * width + c;
        if (occ.count(k)) return -1;

        body.push_front({r, c});
        occ.insert(k);
        if (eat) { foodIdx++; score++; }
        return score;
    }
};

from collections import deque

class SnakeGame:
    def __init__(self, width: int, height: int, food: list[list[int]]):
        self.w = width
        self.h = height
        self.food = food
        self.fi = 0
        self.score = 0
        self.body = deque([(0, 0)])
        self.occ = {0}

    def move(self, direction: str) -> int:
        r, c = self.body[0]
        if direction == "U": r -= 1
        elif direction == "D": r += 1
        elif direction == "L": c -= 1
        else: c += 1

        if r < 0 or r >= self.h or c < 0 or c >= self.w:
            return -1

        eat = self.fi < len(self.food) and [r, c] == self.food[self.fi]
        if not eat:
            tr, tc = self.body.pop()
            self.occ.remove(tr * self.w + tc)

        k = r * self.w + c
        if k in self.occ:
            return -1

        self.body.appendleft((r, c))
        self.occ.add(k)
        if eat:
            self.fi += 1
            self.score += 1
        return self.score

class SnakeGame {
  constructor(width, height, food) {
    this.w = width;
    this.h = height;
    this.food = food;
    this.fi = 0;
    this.score = 0;
    this.body = [[0, 0]];
    this.occ = new Set([0]);
  }

  move(direction) {
    let [r, c] = this.body[0];
    if (direction === "U") r--;
    else if (direction === "D") r++;
    else if (direction === "L") c--;
    else c++;

    if (r < 0 || r >= this.h || c < 0 || c >= this.w) return -1;

    const eat = this.fi < this.food.length && r === this.food[this.fi][0] && c === this.food[this.fi][1];
    if (!eat) {
      const [tr, tc] = this.body.pop();
      this.occ.delete(tr * this.w + tc);
    }

    const k = r * this.w + c;
    if (this.occ.has(k)) return -1;

    this.body.unshift([r, c]);
    this.occ.add(k);
    if (eat) { this.fi++; this.score++; }
    return this.score;
  }
}

中文

题目概述

在二维网格中实现贪吃蛇。每次移动后返回当前分数；若撞墙或撞到自己，返回 -1。

核心思路

用双端队列保存蛇身顺序，用哈希集合保存占用格子做 O(1) 碰撞判断。关键细节是，不吃食物时要先移除尾巴，再判断是否撞到自己。

算法步骤

1）根据方向计算新蛇头。
2）越界直接返回 -1。
3）判断是否吃到当前食物。
4）若没吃到，先弹出尾巴并从集合移除。
5）新头若已在集合中则返回 -1。
6）插入新头；若吃到食物则分数加一。

复杂度分析

单次 move 平均时间复杂度 O(1)，空间复杂度最坏 O(w*h)。

多语言参考实现（Java / Go / C++ / Python / JavaScript）

class SnakeGame {
    private final int width, height;
    private final int[][] food;
    private int foodIndex;
    private int score;
    private final Deque<int[]> body;
    private final Set<Integer> occupied;

    public SnakeGame(int width, int height, int[][] food) {
        this.width = width;
        this.height = height;
        this.food = food;
        this.foodIndex = 0;
        this.score = 0;
        this.body = new ArrayDeque<>();
        this.occupied = new HashSet<>();
        body.addFirst(new int[]{0, 0});
        occupied.add(0);
    }

    public int move(String direction) {
        int[] head = body.peekFirst();
        int nr = head[0], nc = head[1];
        if (direction.equals("U")) nr--;
        else if (direction.equals("D")) nr++;
        else if (direction.equals("L")) nc--;
        else nc++;

        if (nr < 0 || nr >= height || nc < 0 || nc >= width) return -1;

        boolean eat = foodIndex < food.length && nr == food[foodIndex][0] && nc == food[foodIndex][1];
        if (!eat) {
            int[] tail = body.removeLast();
            occupied.remove(tail[0] * width + tail[1]);
        }

        int key = nr * width + nc;
        if (occupied.contains(key)) return -1;

        body.addFirst(new int[]{nr, nc});
        occupied.add(key);

        if (eat) {
            foodIndex++;
            score++;
        }
        return score;
    }
}

type SnakeGame struct {
	width, height int
	food          [][]int
	fi, score     int
	body          [][2]int
	occ           map[int]bool
}

func Constructor(width int, height int, food [][]int) SnakeGame {
	g := SnakeGame{width: width, height: height, food: food, occ: map[int]bool{0: true}}
	g.body = append(g.body, [2]int{0, 0})
	return g
}

func (g *SnakeGame) Move(direction string) int {
	head := g.body[0]
	nr, nc := head[0], head[1]
	switch direction { case "U": nr--; case "D": nr++; case "L": nc--; default: nc++ }
	if nr < 0 || nr >= g.height || nc < 0 || nc >= g.width { return -1 }
	eat := g.fi < len(g.food) && nr == g.food[g.fi][0] && nc == g.food[g.fi][1]
	if !eat {
		tail := g.body[len(g.body)-1]
		g.body = g.body[:len(g.body)-1]
		delete(g.occ, tail[0]*g.width+tail[1])
	}
	k := nr*g.width + nc
	if g.occ[k] { return -1 }
	g.body = append([][2]int{{nr, nc}}, g.body...)
	g.occ[k] = true
	if eat { g.fi++; g.score++ }
	return g.score
}

class SnakeGame {
    int width, height, foodIdx = 0, score = 0;
    vector<vector<int>> food;
    deque<pair<int,int>> body;
    unordered_set<int> occ;
public:
    SnakeGame(int width, int height, vector<vector<int>>& food): width(width), height(height), food(food) {
        body.push_front({0,0});
        occ.insert(0);
    }

    int move(string direction) {
        auto [r, c] = body.front();
        if (direction == "U") r--; else if (direction == "D") r++; else if (direction == "L") c--; else c++;
        if (r < 0 || r >= height || c < 0 || c >= width) return -1;

        bool eat = (foodIdx < (int)food.size() && r == food[foodIdx][0] && c == food[foodIdx][1]);
        if (!eat) {
            auto [tr, tc] = body.back();
            body.pop_back();
            occ.erase(tr * width + tc);
        }

        int k = r * width + c;
        if (occ.count(k)) return -1;

        body.push_front({r, c});
        occ.insert(k);
        if (eat) { foodIdx++; score++; }
        return score;
    }
};

from collections import deque

class SnakeGame:
    def __init__(self, width: int, height: int, food: list[list[int]]):
        self.w = width
        self.h = height
        self.food = food
        self.fi = 0
        self.score = 0
        self.body = deque([(0, 0)])
        self.occ = {0}

    def move(self, direction: str) -> int:
        r, c = self.body[0]
        if direction == "U": r -= 1
        elif direction == "D": r += 1
        elif direction == "L": c -= 1
        else: c += 1

        if r < 0 or r >= self.h or c < 0 or c >= self.w:
            return -1

        eat = self.fi < len(self.food) and [r, c] == self.food[self.fi]
        if not eat:
            tr, tc = self.body.pop()
            self.occ.remove(tr * self.w + tc)

        k = r * self.w + c
        if k in self.occ:
            return -1

        self.body.appendleft((r, c))
        self.occ.add(k)
        if eat:
            self.fi += 1
            self.score += 1
        return self.score

class SnakeGame {
  constructor(width, height, food) {
    this.w = width;
    this.h = height;
    this.food = food;
    this.fi = 0;
    this.score = 0;
    this.body = [[0, 0]];
    this.occ = new Set([0]);
  }

  move(direction) {
    let [r, c] = this.body[0];
    if (direction === "U") r--;
    else if (direction === "D") r++;
    else if (direction === "L") c--;
    else c++;

    if (r < 0 || r >= this.h || c < 0 || c >= this.w) return -1;

    const eat = this.fi < this.food.length && r === this.food[this.fi][0] && c === this.food[this.fi][1];
    if (!eat) {
      const [tr, tc] = this.body.pop();
      this.occ.delete(tr * this.w + tc);
    }

    const k = r * this.w + c;
    if (this.occ.has(k)) return -1;

    this.body.unshift([r, c]);
    this.occ.add(k);
    if (eat) { this.fi++; this.score++; }
    return this.score;
  }
}