LeetCode 筆記：生命遊戲 原地演算法詳解

一、題目描述

根據 Conway 的「生命遊戲」規則，給定 m × n 二進制矩陣（1=活、0=死），計算下一狀態。規則：

1. 活細胞鄰居 < 2 → 死（孤獨）
2. 活細胞鄰居 2 或 3 → 活
3. 活細胞鄰居 > 3 → 死（擁擠）
4. 死細胞鄰居 == 3 → 活（繁殖）

要求 原地修改，不可用額外矩陣。

二、狀態編碼技巧

因為更新時需同時知曉「原狀態」與「新狀態」，引入中間狀態碼：

第一遍掃描：根據原狀態（val == 1 || val == 2 視為原活）計算鄰居數，寫入中間碼。
第二遍掃描：所有值 % 2，0/2→死，1/3→活。

三、示例代碼

class Solution {
public:
    void gameOfLife(vector>& board) {
        int m = board.size(); if (!m) return;
        int n = board[0].size(); if (!n) return;
        // 方向向量：8 鄰域
        const int dx[8] = {-1,-1,-1,0,0,1,1,1};
        const int dy[8] = {-1,0,1,-1,1,-1,0,1};

        for (int i = 0; i < m; ++i) {
            for (int j = 0; j < n; ++j) {
                int live = 0;
                for (int d = 0; d < 8; ++d) {
                    int x = i + dx[d], y = j + dy[d];
                    if (x >= 0 && x < m && y >= 0 && y < n &&
                        (board[x][y] == 1 || board[x][y] == 2))
                        ++live;
                }
                if (board[i][j] == 1) { // 原活
                    if (live < 2 || live > 3) board[i][j] = 2; // 變死
                } else { // 原死
                    if (live == 3) board[i][j] = 3; // 變活
                }
            }
        }
        // 還原最終狀態
        for (int i = 0; i < m; ++i)
            for (int j = 0; j < n; ++j)
                board[i][j] %= 2;
    }
};

四、複雜度與小結

• 時間：O(m × n)，兩次完整掃描。
• 空間：O(1)，原地修改，無額外數組。
• 核心思想：狀態壓縮，用高位保存舊狀態，低位寫入新狀態，最後移位或取模還原。此技巧常用於原地矩陣轉換問題。