文章目錄
- 摘要
- 描述
- 解決方案
- 解析問題與解決方案
- 關鍵細節逐條講
- 示例與運行結果
- 時間復雜度
- 空間復雜度
- 總結
摘要
這題的目標是設計一個“貪吃蛇”核心引擎：給定棋盤大小和一串食物位置，支持不斷調用 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 里的坐標把節點畫出來即可；引擎層完全復用本文代碼。
