289. Game of Life

題目 / Problem

中文：給定一個 m x n 的網格 board，每個格子是 活 (1) 或 死 (0)。每個格子有 8 個鄰居（上下、左右、四個對角線）。同時對所有格子套用以下 4 條規則，產生「下一代」的盤面：

1. 活細胞若周圍活鄰居 少於 2 個，因「人口不足」而死亡。
2. 活細胞若周圍有 2 或 3 個 活鄰居，存活到下一代。
3. 活細胞若周圍活鄰居 超過 3 個，因「人口過多」而死亡。
4. 死細胞若周圍 剛好 3 個 活鄰居，因「繁殖」而復活。

關鍵字是 同時 (simultaneously)：所有出生與死亡是基於「當前」盤面同時發生的，你不能更新一部分後再用更新後的值去算其他格子。請 原地修改 board，不需回傳任何東西。

English: You are given an m x n grid board where each cell is live (1) or dead (0). Each cell looks at its 8 neighbors (horizontal, vertical, diagonal). Apply these 4 rules to every cell simultaneously to compute the next generation:

1. A live cell with fewer than 2 live neighbors dies (under-population).
2. A live cell with 2 or 3 live neighbors lives on.
3. A live cell with more than 3 live neighbors dies (over-population).
4. A dead cell with exactly 3 live neighbors becomes alive (reproduction).

The crucial word is simultaneously: every birth/death is decided from the original board, not from partially-updated values. Update board in place; return nothing.

Constraints - m == board.length, n == board[i].length - 1 <= m, n <= 25 - board[i][j] is 0 or 1.

Example

Input:  board = [[0,1,0],[0,0,1],[1,1,1],[0,0,0]]
Output: [[0,0,0],[1,0,1],[0,1,1],[0,1,0]]

名詞解釋 / Glossary

• 細胞自動機 / Cellular automaton：一個由格子組成的系統，每個格子依照固定規則和鄰居的狀態一起演化。Game of Life 是最有名的例子。
• 8-鄰居 / Moore neighborhood：一個格子周圍的 8 個格子（上、下、左、右、以及 4 個對角線）。本題的「鄰居」就是指這 8 個。
• 原地修改 / In-place：直接在原本的陣列上修改，不額外開一個同樣大小的新陣列。額外空間只用 O(1)。
• 位元編碼 / Bit encoding：用一個整數的不同二進位位元（bit）同時存兩份資訊。這裡用「第 0 位」存當前狀態，「第 1 位」存下一代狀態，這樣就能在同一個格子裡保留新舊兩個值。
• 位元運算 / Bitwise operators：&（AND，取出某些位元）、|（OR，設定某些位元）、<<（左移，把 1 推到第 1 位變成 2）、>>（右移，把第 1 位移回第 0 位）。
• 邊界檢查 / Bounds checking：數鄰居時要確認鄰居座標 (r, c) 沒有跑出網格範圍 0 <= r < m、0 <= c < n，否則會讀到陣列外的非法記憶體。

思路

最直覺的暴力法是：另外開一個和 board 一樣大的新陣列 next，對每個格子數它在「原盤面」上的活鄰居數，把結果寫進 next，最後再把 next 整個複製回 board。這樣完全正確，因為我們讀的永遠是沒被改動過的原盤面，自然滿足「同時更新」。缺點是用了 O(m·n) 的額外空間，而 follow-up 問我們能不能 原地 做。

要原地做，難點在於：如果我直接把某格從 1 改成 0，那麼它右邊的格子在數鄰居時就會讀到已經被改過的值，違反「同時」。解法是用 位元編碼 把新舊兩個狀態塞進同一個整數。每個格子原本只用到第 0 位（值是 0 或 1）。我們約定：第 1 位 存「下一代」狀態。掃描時用 board[i][j] & 1 永遠能讀回「原始」狀態，因為我們只在第 1 位寫新值，從不破壞第 0 位。算出某格下一代是活的，就用 board[i][j] |= 2（把第 1 位設成 1）。全部掃完後，再把每格 board[i][j] >>= 1（右移一位），把存在第 1 位的新狀態移到第 0 位，舊狀態就被丟掉了。這樣只用 O(1) 額外空間，且因為讀取始終靠第 0 位，完美保證了同時性。

The brute-force idea is: allocate a second grid next of the same size, count each cell's live neighbors using the original board, write the result into next, then copy next back into board. It's correct because we always read the unmodified board, so updates are effectively simultaneous — but it costs O(m·n) extra space, and the follow-up asks for an in-place solution. The obstacle to going in-place is that overwriting a 1 with a 0 corrupts the value its neighbors still need to read. The trick is bit encoding: pack both the old and new state into one integer per cell. Bit 0 already holds the current state; we reserve bit 1 for the next state. During the scan, board[i][j] & 1 always recovers the original value because we only ever set bit 1 and never touch bit 0. When a cell should be alive next generation, we do board[i][j] |= 2 to turn bit 1 on. After the full sweep, a second pass does board[i][j] >>= 1 to shift the stored next-state from bit 1 down into bit 0, discarding the old value. This uses O(1) extra space, and because every read goes through bit 0, simultaneity is guaranteed.

逐步走查 / Walkthrough

用第一個範例 board = [[0,1,0],[0,0,1],[1,1,1],[0,0,0]]（4 列 3 行 / 4 rows, 3 cols）。座標用 (row, col)，索引從 0 開始。

我們對每格用 & 1 數原始活鄰居數 live，再依規則決定下一代是否活；若活就把第 1 位設起來（值 +2）。下表只列出幾個代表性的格子 / The table shows representative cells:

第一遍掃完後，盤面（編碼值）大致變成混合了 0/1/2/3 的整數。第二遍對每格做 >>= 1： - 0 >> 1 = 0，1 >> 1 = 0（舊活、新死） - 2 >> 1 = 1（舊死、新活），3 >> 1 = 1（舊活、新活）

最終得到 [[0,0,0],[1,0,1],[0,1,1],[0,1,0]]，與預期輸出相符 / matching the expected output.

關鍵觀察：在第一遍中，(1,0) 已被改成 2，但當我們後來處理它的鄰居時，用 2 & 1 = 0 仍讀到它的原始值 0，所以不會出錯 / Key point: even after (1,0) became 2, reading it later via 2 & 1 = 0 still returns its original value, so neighbors are unaffected.

Solution — C

// 演算法 / Algorithm:
// 用位元編碼原地更新：第 0 位存當前狀態，第 1 位存下一代狀態。
// Bit-encode in place: bit 0 = current state, bit 1 = next state.
// 第一遍依規則設第 1 位；第二遍右移一位，把下一代移到第 0 位。
// Pass 1 sets bit 1 by the rules; pass 2 shifts right to reveal the next gen.

void gameOfLife(int** board, int boardSize, int* boardColSize) {
    int m = boardSize;            // 列數 / number of rows
    int n = boardColSize[0];      // 行數（每列等長）/ number of columns (rows are equal length)

    // 8 個鄰居的相對位移：dx 是列差、dy 是行差 / relative offsets of the 8 neighbors
    int dx[8] = {-1, -1, -1,  0, 0,  1, 1, 1};
    int dy[8] = {-1,  0,  1, -1, 1, -1, 0, 1};

    // 第一遍：計算每格的下一代狀態，存進第 1 位 / Pass 1: compute next state into bit 1
    for (int i = 0; i < m; i++) {
        for (int j = 0; j < n; j++) {
            int live = 0;  // 這格周圍的活鄰居數 / count of live neighbors

            // 檢查 8 個方向 / scan all 8 directions
            for (int k = 0; k < 8; k++) {
                int r = i + dx[k];   // 鄰居的列座標 / neighbor row
                int c = j + dy[k];   // 鄰居的行座標 / neighbor col

                // 邊界檢查：座標必須在網格內，否則跳過 / bounds check before reading
                if (r >= 0 && r < m && c >= 0 && c < n) {
                    // & 1 取出「原始」狀態（第 0 位），不受第 1 位被改動影響
                    // & 1 extracts the ORIGINAL state (bit 0), immune to bit-1 edits
                    live += board[r][c] & 1;
                }
            }

            // board[i][j] & 1 是這格自己的原始狀態 / this cell's own original state
            if (board[i][j] & 1) {
                // 規則 2：活細胞有 2 或 3 個活鄰居 → 下一代仍活
                // Rule 2: a live cell with 2 or 3 live neighbors stays alive
                if (live == 2 || live == 3) {
                    board[i][j] |= 2;   // |= 2 把第 1 位設為 1（標記下一代為活）/ set bit 1 = alive next
                }
                // 否則第 1 位維持 0（下一代死）/ otherwise bit 1 stays 0 (dead next)
            } else {
                // 規則 4：死細胞剛好 3 個活鄰居 → 復活
                // Rule 4: a dead cell with exactly 3 live neighbors is born
                if (live == 3) {
                    board[i][j] |= 2;   // 同樣設第 1 位 / mark next state alive
                }
            }
        }
    }

    // 第二遍：右移一位，丟掉舊狀態，留下下一代 / Pass 2: shift right to keep only next gen
    for (int i = 0; i < m; i++) {
        for (int j = 0; j < n; j++) {
            board[i][j] >>= 1;   // >>= 1 把第 1 位移到第 0 位 / move bit 1 down to bit 0
        }
    }
}

Solution — C++

// 演算法 / Algorithm:
// 與 C 版相同的位元編碼原地解法：第 0 位 = 當前，第 1 位 = 下一代。
// Same in-place bit trick as C: bit 0 = current, bit 1 = next generation.
// 改用 vector 與 range-based 索引，風格更現代 C++ / written in idiomatic C++.

class Solution {
public:
    void gameOfLife(vector<vector<int>>& board) {
        int m = board.size();       // 列數 / number of rows
        int n = board[0].size();    // 行數 / number of columns

        // 8 個鄰居的相對位移 / the 8 neighbor offsets as {drow, dcol} pairs
        // 這是一個固定的常數陣列 / a small constant lookup table
        const int dir[8][2] = {{-1,-1},{-1,0},{-1,1},{0,-1},
                               {0,1},{1,-1},{1,0},{1,1}};

        // 第一遍：算下一代狀態，存進第 1 位 / Pass 1: encode next state into bit 1
        for (int i = 0; i < m; ++i) {
            for (int j = 0; j < n; ++j) {
                int live = 0;  // 活鄰居數 / live-neighbor count

                // range-for：依序取出每組位移 (d[0]=列差, d[1]=行差)
                // range-based for loop over the offset table
                for (const auto& d : dir) {
                    int r = i + d[0];   // 鄰居列 / neighbor row
                    int c = j + d[1];   // 鄰居行 / neighbor col

                    // 邊界檢查後，用 & 1 讀原始狀態 / read original state via bit 0
                    if (r >= 0 && r < m && c >= 0 && c < n)
                        live += board[r][c] & 1;
                }

                int cur = board[i][j] & 1;   // 這格的原始狀態 / this cell's original state

                // 活著且(2或3鄰居)，或 死著且剛好3鄰居 → 下一代為活
                // Alive & (2 or 3) OR dead & exactly 3 → alive next generation
                if ((cur == 1 && (live == 2 || live == 3)) ||
                    (cur == 0 && live == 3)) {
                    board[i][j] |= 2;        // 設第 1 位標記下一代為活 / set bit 1
                }
            }
        }

        // 第二遍：右移一位取出下一代 / Pass 2: shift each cell right by 1
        for (auto& row : board)          // range-for 取每一列的參考 / reference to each row
            for (int& cell : row)        // int& 取每格的參考，可直接修改 / mutable reference
                cell >>= 1;              // 把第 1 位移回第 0 位 / bit 1 → bit 0
    }
};

複雜度 / Complexity

• Time: O(m·n) — 我們對每個格子各掃描一次來數鄰居，每次數鄰居是固定的 8 次（常數），第二遍右移又是 O(m·n)。總共與格子總數成正比。/ We visit every cell once; counting neighbors is a constant 8 checks per cell, and the shift pass is another O(m·n). Dominated by the number of cells m·n.
• Space: O(1) — 沒有開新陣列，所有新狀態都暫存在原格子的第 1 位裡，只用了幾個固定變數。/ No extra grid; the next state is stashed inside each cell's bit 1, using only a handful of fixed variables.

Pitfalls & Edge Cases

• 同時更新 / Simultaneous update：最大的陷阱是直接把 1 改成 0，後面的鄰居就讀到錯誤值。用 & 1 只讀第 0 位（原始值）、用 |= 2 只寫第 1 位，兩者互不干擾，這就避開了陷阱。/ Overwriting cells directly corrupts neighbor reads; bit encoding keeps old and new states separate.
• 忘記第二遍右移 / Forgetting the shift pass：若只做第一遍，盤面會留下 2 和 3 這種「兩位編碼」的值，不是合法的 0/1。一定要記得 >>= 1。/ Without >>= 1 the board still contains encoded 2/3 values instead of 0/1.
• 邊界外存取 / Out-of-bounds access：數鄰居時若不檢查 r, c 是否在 [0,m)×[0,n) 內，會讀到陣列外記憶體，造成崩潰或錯誤計數。每次讀鄰居前都先做邊界檢查。/ Always bounds-check neighbor coordinates before indexing.
• n 必須從 board 取得 / Get n correctly：C 版的行數來自 boardColSize[0]，不要寫死。題目保證每列等長 (n == board[i].length)，所以取第 0 列的長度即可。/ In C, read the column count from boardColSize[0], not a hardcoded value.
• 1×1 等極小盤面 / Tiny boards：m 或 n 可能為 1。單一活細胞沒有任何活鄰居 → 下一代死亡；演算法自然處理，無需特判。/ A lone live cell has 0 live neighbors and dies — handled without special cases.