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