LeetCode 353. 贪吃蛇

2023-02-22 HGNULB 约 7 分钟

文章信息 8 个分类 5 个标签

分类

LeetCode CodeTop 中等未解决会员题 2-5 字节微软

题目描述

✅ 353. 贪吃蛇

题意分析

蛇初始只占左上角 (0, 0) 一格，按 U、D、L、R 每次移动一格。食物按给定顺序逐个出现：吃到当前食物时长度和得分各加一，否则长度不变。撞墙或撞到未腾出的身体格子时游戏结束，返回 -1；成功移动返回当前得分，结束后的调用仍返回 -1。

解法：队列 + 哈希集合模拟

核心思路

[!blue]

移动需要同时知道身体顺序和某个格子是否被占用。用双端队列 body 从队首到队尾保存蛇尾到蛇头，用集合 occupied 保存同一批格子。队列负责移尾、加头，集合负责快速判断自撞；两者必须同步更新。

将合法坐标编码为 row * width + col，就能用一个整数放入队列和集合，并用除法、取余恢复行列。每次先根据旧蛇头和方向算出新坐标，检查二维边界，再判断它是否等于 food[foodIndex]；后面的食物尚未出现，不能提前吃掉。

碰撞判断必须对应本次移动完成后的身体。如果没有吃到食物，旧尾巴会同时前移，因此先从队列和集合中移除旧尾，再检查新头是否占用。这样新头可以合法进入刚腾出的旧尾格。若吃到食物，尾巴不动，必须保留它再检查碰撞。

新头未撞到身体时，将它加入队尾和集合；吃到食物则增加得分，并推进 foodIndex。未进食时先删一格再加一格，长度不变；进食时只加头不移尾，长度增加一。每次成功移动后，队列顺序与占用集合仍表示同一条蛇。

两种碰撞都把 gameOver 设为真。每次调用首先检查该状态，已结束就直接返回 -1，避免失败后继续读取或修改身体。食物耗尽后不再读取食物数组，后续成功移动都按不增长处理。

解题步骤

初始化蛇身和集合为位置 0，食物下标与得分均为 0。

每次移动先检查结束状态，再计算新蛇头坐标；越界则记录结束并返回 -1。

判断是否吃到当前食物；若未吃到，同步删除队首蛇尾及其占用标记。

若新头仍在占用集合中，记录结束并返回 -1；否则将新头加入队尾与集合。

若吃到食物，增加得分和食物下标，最后返回得分。

代码实现

class SnakeGame {
    private final int width;
    private final int height;
    private final int[][] food;
    private int foodIndex;
    private int score;
    private boolean gameOver;
    private final Deque<Integer> 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.addLast(0);
        occupied.add(0);
    }

    public int move(String direction) {
        // 结束状态不可恢复，后续调用不再改变身体
        if (gameOver) {
            return -1;
        }

        int head = body.peekLast();
        int r = head / width;
        int c = head % width;

        switch (direction) {
            case "U":
                r--;
                break;
            case "D":
                r++;
                break;
            case "L":
                c--;
                break;
            default:
                c++;
                break;
        }

        if (r < 0 || r >= height || c < 0 || c >= width) {
            gameOver = true;

            return -1;
        }

        int next = r * width + c;
        boolean eating =
                foodIndex < food.length && food[foodIndex][0] == r && food[foodIndex][1] == c;

        // 不增长时尾格先腾出，允许新头进入原尾格
        if (!eating) {
            int tail = body.pollFirst();

            occupied.remove(tail);
        }

        if (occupied.contains(next)) {
            gameOver = true;

            return -1;
        }

        body.addLast(next);
        occupied.add(next);

        if (eating) {
            score++;
            foodIndex++;
        }

        return score;
    }
}

import "container/list"

type SnakeGame struct {
    width     int
    height    int
    food      [][]int
    foodIndex int
    score     int
    gameOver  bool
    body      *list.List
    occupied  map[int]bool
}

func Constructor(width int, height int, food [][]int) SnakeGame {
    body := list.New()
    body.PushBack(0)

    return SnakeGame{
        width:     width,
        height:    height,
        food:      food,
        foodIndex: 0,
        score:     0,
        body:      body,
        occupied:  map[int]bool{0: true},
    }
}

func (g *SnakeGame) Move(direction string) int {
    // 结束状态不可恢复，后续调用不再改变身体
    if g.gameOver {
        return -1
    }

    head := g.body.Back().Value.(int)
    r := head / g.width
    c := head % g.width

    switch direction {
    case "U":
        r--
    case "D":
        r++
    case "L":
        c--
    default:
        c++
    }

    if r < 0 || r >= g.height || c < 0 || c >= g.width {
        g.gameOver = true
        return -1
    }

    next := r*g.width + c
    eating := g.foodIndex < len(g.food) && g.food[g.foodIndex][0] == r && g.food[g.foodIndex][1] == c

    // 不增长时尾格先腾出，允许新头进入原尾格
    if !eating {
        tail := g.body.Front()
        g.body.Remove(tail)
        delete(g.occupied, tail.Value.(int))
    }

    if g.occupied[next] {
        g.gameOver = true
        return -1
    }

    g.body.PushBack(next)
    g.occupied[next] = true

    if eating {
        g.score++
        g.foodIndex++
    }

    return g.score
}

复杂度分析

时间复杂度：每次移动期望均摊 $O(1)$，只进行固定次数的双端队列与哈希操作。

空间复杂度：$O(\min(wh,F+1))$，w、h 为棋盘宽高，F 为食物数量。蛇长不超过棋盘格数，也不超过初始一节加已吃食物数；不计输入食物表。

关键点总结

[!green]

身体顺序与占用集合负责不同查询，必须同步更新。

增长与不增长决定尾格是否在本次仍被占用。

易错点总结

[!yellow]

未增长时先判撞，会错误拒绝进入旧尾格。

增长时仍移尾，蛇不会变长。

食物下标耗尽后仍读取，会越界。

碰撞只返回负一却不记录终止状态，会让后续调用继续游戏。

只检查线性编码是否越界，可能把左右越界误当成相邻行的合法格子；应先检查行列。

相似题目

题目	难度	关联与区别
622. 设计循环队列	中等	蛇身可用队列维护头尾；未吃到食物时头进尾出，吃到食物时保留蛇尾以增长，本题还需集合判断身体碰撞。

转载与许可

作者 HGNULB

链接 https://hgnulb.github.io/blog/2023/94878234

许可本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！