摘要

你有沒有想過，能不能通過簡單的規則模擬出生與死亡？「生命游戲」正是這樣一種充滿魅力的數學模擬系統。這篇文章我們來聊聊它的規則到底有多神奇，并用 Swift 實現一個原地更新的算法，完全不需要額外內存空間，還能用得很優雅。如果你是算法練習者或者對模型仿真感興趣，這篇你一定不能錯過。

描述

生命游戲最早由數學家 John Conway 提出，是一種“零玩家游戲”。什么意思？就是說，一旦設置好初始狀態，系統會自動演化，不再需要人為干預。

我們把一個二維網格當作世界，每個格子就是一個細胞。每個細胞的狀態可能是“活”或“死”，狀態變化完全依賴它周圍八個鄰居的狀態。核心的規則有這幾條：

1. 活細胞周圍活鄰居少于 2 個 → 死（孤獨）
2. 活細胞周圍 2 或 3 個活鄰居 → 繼續活著
3. 活細胞周圍超過 3 個活鄰居 → 死（過度擁擠）
4. 死細胞周圍恰好有 3 個活鄰居 → 復活！

所以我們要做的就是根據這四條規則，在原數組上進行原地更新，生成下一輪的世界。

題解答案

我們使用一個小技巧來原地記錄狀態的變化：

• 活→死 用 -1 表示
• 死→活 用 2 表示

這樣我們在遍歷的時候可以保留舊狀態（通過 abs(board[i][j]) 取得），等所有狀態都計算完之后再統一轉換回 0 或 1。

題解代碼分析

func gameOfLife(_ board: inout [[Int]]) {let m = board.countlet n = board[0].countlet directions = [(-1,-1), (-1,0), (-1,1),( 0,-1),         ( 0,1),( 1,-1), ( 1,0), ( 1,1)]for i in 0..<m {for j in 0..<n {var liveNeighbors = 0// 統計活鄰居數量for dir in directions {let x = i + dir.0let y = j + dir.1if x >= 0 && x < m && y >= 0 && y < n {if abs(board[x][y]) == 1 {liveNeighbors += 1}}}// 應用規則if board[i][j] == 1 && (liveNeighbors < 2 || liveNeighbors > 3) {board[i][j] = -1 // 活→死}if board[i][j] == 0 && liveNeighbors == 3 {board[i][j] = 2 // 死→活}}}// 最終狀態統一替換for i in 0..<m {for j in 0..<n {board[i][j] = board[i][j] > 0 ? 1 : 0}}
}

示例測試及結果

我們用幾個例子跑一下看看效果。

var board1 = [[0,1,0],[0,0,1],[1,1,1],[0,0,0]]gameOfLife(&board1)
print(board1)
// 輸出：[[0,0,0],[1,0,1],[0,1,1],[0,1,0]]var board2 = [[1,1],[1,0]]gameOfLife(&board2)
print(board2)
// 輸出：[[1,1],[1,1]]

你可以把這段代碼直接貼到 Xcode Playground 或命令行 Swift 項目里跑一跑，觀察每輪世界的變化，非常直觀。

時間復雜度

我們遍歷了整個二維數組一次，并對每個元素最多再遍歷 8 個鄰居，所以：

時間復雜度：O(m * n)
其中 m 和 n 是二維數組的行數和列數。

空間復雜度

我們沒有使用額外的數組，只是在原數組中用 -1 和 2 來標記變化。

空間復雜度：O(1)（原地算法）

總結

“生命游戲”聽起來像是一種編程游戲，但其實它也是模擬系統、分布式模型、甚至人工生命研究中的一個縮影。通過這種原地算法優化，我們不僅節省空間，還能更貼近“狀態轉移”的本質。

這道題的亮點在于如何處理狀態切換時的數據保存問題，如果直接改掉原始數據，我們就沒法知道舊值是否活著。而用 -1 和 2 的技巧正好幫我們保留了歷史信息，最終只需一輪替換就能搞定。