// 演算法 / 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
    }
};