文章目录
- 摘要
- 描述
- 解决方案
- 解析问题与解决方案
- 关键细节逐条讲
- 示例与运行结果
- 时间复杂度
- 空间复杂度
- 总结
摘要
这题的目标是设计一个“贪吃蛇”核心引擎：给定棋盘大小和一串食物位置，支持不断调用 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: Tvar 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 = 0var isEmpty: Bool { count == 0 }func pushBack(_ v: T) {let node = Node(v)if let t = tail {t.next = nodenode.prev = ttail = node} else {head = nodetail = node}count += 1}func popFront() -> T? {guard let h = head else { return nil }let v = h.vallet nh = h.nextnh?.prev = nilhead = nhif nh == nil { tail = nil }count -= 1return v}func back() -> T? { tail?.val }func front() -> T? { head?.val }
}// 核心：SnakeGame
final class SnakeGame {private let width: Intprivate let height: Intprivate let food: [[Int]]private var foodIndex: Int = 0// 蛇身：尾在 front，头在 backprivate 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 = widthself.height = heightself.food = food// 初始蛇：长度为 1，在 (0,0)let startId = 0body.pushBack(startId)occupied.insert(startId)score = 0foodIndex = 0}// 坐标与一维 id 的互转private func idOf(_ r: Int, _ c: Int) -> Int { r * width + c }private func rcOf(_ id: Int) -> (Int, Int) { (id / width, id % width) }// 一步移动：返回当前分数，若失败返回 -1func 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 + drlet 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 += 1foodIndex += 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")) // 0print(game.move("D")) // 0print(game.move("R")) // 1 (吃到 [1,2])print(game.move("U")) // 1print(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")) // 1print(game.move("R")) // 2print(game.move("R")) // 3print(game.move("D")) // 3print(game.move("L")) // 3print(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 里的坐标把节点画出来即可；引擎层完全复用本文代码。
