摘要
这题的目标是设计一个“贪吃蛇”核心引擎：给定棋盘大小和一串食物位置，支持不断调用 move(direction) 推进游戏，返回当前分数，撞墙或咬到自己就结束（返回 -1）。本文用 Swift 从零实现一个能跑起来的 Demo，包括完整的 SnakeGame 类、关键数据结构设计、边界与碰撞处理、以及几组样例跑数。代码贴近实战，既能交作业，也能当你写小型游戏/面试题的参考模板。
描述
题目要我们实现三个能力：
SnakeGame(width, height, food): 初始化棋盘和食物队列。move(direction: String) -> Int: 让蛇向U/D/L/R走一步；- 吃到食物：长度 +1，分数 +1。
- 普通移动：头前进一格，尾巴同时挪走一格。
- 撞墙/咬到自己：返回 -1（游戏结束）。
返回值：当前分数（吃到几次食物）。若结束，始终返回 -1。
要点在于：如何让每次 move 都保持 O(1) 或接近 O(1) 的时间复杂度。
解决方案
高效思路（也是业界常见写法）：
双端结构存蛇身：
用一个可 O(1) 头插、尾删的结构维护蛇身顺序（头在尾端更直观），我们用一个简易的 双向链表。快速查重靠哈希集合：
用Set存蛇身占用的格子，一步就能判断“咬到自己”。一维编码坐标：
位置(r, c)编码为id = r * width + c。既省内存又快。先判断是否吃到食物：
- 吃到：不移除尾巴（蛇变长）。
- 没吃到：先把尾巴从集合里移除（因为尾巴会移动），再判断新头是否与身体冲突。
边界/自撞检查：
- 越界直接结束。
- 自撞：若新头位置已经在集合里（注意“没吃到食物”的情况下我们先拿掉尾巴再查重）。
解析问题与解决方案
下面是完整可运行的 Swift 代码（命令行/Playground 都能跑）。为了 O(1) 头插尾删，我们写了个轻量的双向链表 Deque；蛇身用 Deque<Int> 维护，哈希表记录占用。
import Foundation
// 轻量双向链表（Deque）——支持 O(1) 头删尾插等操作
final class Deque<T> {
final class Node<T> {
var val: T
var prev: Node<T>?
var next: Node<T>?
init(_ v: T) { self.val = v }
}
private var head: Node<T>?
private var tail: Node<T>?
private(set) var count: Int = 0
var isEmpty: Bool { count == 0 }
func pushBack(_ v: T) {
let node = Node(v)
if let t = tail {
t.next = node
node.prev = t
tail = node
} else {
head = node
tail = node
}
count += 1
}
func popFront() -> T? {
guard let h = head else { return nil }
let v = h.val
let nh = h.next
nh?.prev = nil
head = nh
if nh == nil { tail = nil }
count -= 1
return v
}
func back() -> T? { tail?.val }
func front() -> T? { head?.val }
}
// 核心：SnakeGame
final class SnakeGame {
private let width: Int
private let height: Int
private let food: [[Int]]
private var foodIndex: Int = 0
// 蛇身：尾在 front，头在 back
private var body = Deque<Int>()
// 占用表：快速判断“撞到自己”
private var occupied = Set<Int>()
private var score = 0
// 方向映射
private let dirMap: [String: (Int, Int)] = [
"U": (-1, 0), "D": (1, 0),
"L": (0, -1), "R": (0, 1)
]
init(_ width: Int, _ height: Int, _ food: [[Int]]) {
self.width = width
self.height = height
self.food = food
// 初始蛇：长度为 1，在 (0,0)
let startId = 0
body.pushBack(startId)
occupied.insert(startId)
score = 0
foodIndex = 0
}
// 坐标与一维 id 的互转
private func idOf(_ r: Int, _ c: Int) -> Int { r * width + c }
private func rcOf(_ id: Int) -> (Int, Int) { (id / width, id % width) }
// 一步移动：返回当前分数，若失败返回 -1
func move(_ direction: String) -> Int {
guard let (dr, dc) = dirMap[direction] else { return -1 }
guard let headId = body.back() else { return -1 }
let (hr, hc) = rcOf(headId)
let nr = hr + dr
let nc = hc + dc
// 1) 越界？
if nr < 0 || nr >= height || nc < 0 || nc >= width {
return -1
}
let newHead = idOf(nr, nc)
// 2) 是否吃到食物？
let willEat = (foodIndex < food.count &&
food[foodIndex][0] == nr &&
food[foodIndex][1] == nc)
// 3) 如果不会吃到，尾巴要移动：先从占用表移除尾巴
if !willEat {
if let tailId = body.front() {
_ = body.popFront()
occupied.remove(tailId)
}
}
// 4) 自撞？
if occupied.contains(newHead) {
return -1
}
// 5) 头前进：加入蛇身与占用表
body.pushBack(newHead)
occupied.insert(newHead)
// 6) 吃到食物：分数+1，食物指针后移
if willEat {
score += 1
foodIndex += 1
}
return score
}
}
关键细节逐条讲
为什么先“挪尾再查撞”？
蛇不吃的时候，下一步尾巴会离开原位置。所以你可以“允许头移动到原尾巴位置”。实现上就表现为：先把尾巴从occupied里移除，再查新头是否在occupied。这能避免错判“咬到自己”。数据结构选型
Deque：我们只需要 O(1) 地在“尾部加头”、“头部去尾”，链表最直觉；自己实现很轻，避免Array.removeFirst()的 O(n)。Set：哈希查重 O(1)，非常关键。- 一维编码位置：让
Set<Int>更轻量，少了元组 hash 的开销。
食物逻辑
- “吃到食物不移除尾巴”是增长的本质。
foodIndex单调递增就行，省去额外数据结构。
方向映射
简单Dictionary，易于拓展（比如以后加入斜向就是改这儿）。
示例与运行结果
下面给一段可运行的 Demo，包含两组测试：一组是经典样例，一组是我自定义的压力测试（快速吃两个食物、触发自撞）。
// MARK: - Demo 1（LeetCode 常见用例）
do {
let game = SnakeGame(3, 2, [[1,2],[0,1]])
print("Demo 1")
print(game.move("R")) // 0
print(game.move("D")) // 0
print(game.move("R")) // 1 (吃到 [1,2])
print(game.move("U")) // 1
print(game.move("L")) // 2 (吃到 [0,1])
print(game.move("U")) // -1 (撞墙)
print("----")
}
// MARK: - Demo 2（连续吃食物 + 自撞）
do {
let game = SnakeGame(4, 3, [[0,1],[0,2],[0,3]])
print("Demo 2")
print(game.move("R")) // 1
print(game.move("R")) // 2
print(game.move("R")) // 3
print(game.move("D")) // 3
print(game.move("L")) // 3
print(game.move("U")) // -1（向上回到自己身体）
print("----")
}
可能输出（你的控制台应该是一致的）：
Demo 1
0
0
1
1
2
-1
----
Demo 2
1
2
3
3
3
-1
----
你可以在 Playground 或命令行直接复制粘贴运行，感受一下每一步的状态变化。
时间复杂度
每次
move：
全部是 O(1) 操作：- 链表尾插/头删 O(1)
Set增删查 O(1)- 一次边界和食物判断 O(1)
因此整题可以轻松达到 均摊 O(1)。
初始化：
O(1)（食物数组只是引用，未做预处理）。
空间复杂度
- 蛇身链表：最多占用 O(k)（k 为当前蛇长）。
- 占用集合：同样 O(k)。
- 食物数组：O(f)（f 为食物个数）。
- 其他都是常数。
整体空间：O(k + f)。
总结
这道题表面是小游戏，实则是数据结构设计题。抓住三件事就能写得又快又稳：
- 用 Deque + Set 保证 O(1) 移动与查重；
- “不吃时先挪尾巴再查撞”这一步是避免误判的关键；
- 一维编码位置提升哈希效率，让实现更简洁。
如果你以后要把它扩展成单机小游戏，渲染层（SwiftUI、SpriteKit）只需要消费 move 的结果，按照 Deque 里的坐标把节点画出来即可；引擎层完全复用本文代码。