題目規則

康威生命遊戲：m×n 網格，每細胞生(1)/死(0)。根據 8 鄰居活細胞數演化：

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

要求原地更新（同步演化，不能先更新後用新值影響鄰居）。進階：無限網格邊界處理。

核心技巧：位編碼同步更新

用個位存當前狀態，十位存下一狀態：

• 計算鄰居活數時：board[i][j] % 10 取當前狀態
• 判斷下一狀態為活：board[i][j] += 10
• 統一更新：board[i][j] /= 10

巧妙避免額外數組，滿足 O(1) 空間（不計輸入）。

完整代碼

// C++ 版本 Runtime: 4 ms
class Solution {
public:
    void gameOfLife(vector<vector<int>>& board) {
        int m = board.size(), n = board[0].size();
        // 第一遍：計算下一狀態存入十位
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                int live = countLive(board, i, j);
                if (board[i][j] == 1 && (live == 2 || live == 3) ||
                    board[i][j] == 0 && live == 3) {
                    board[i][j] += 10; // 標記下一代為活
                }
            }
        }
        // 第二遍：統一更新
        for (int i = 0; i < m; i++)
            for (int j = 0; j < n; j++)
                board[i][j] /= 10;
    }
private:
    int countLive(vector<vector<int>>& board, int x, int y) {
        int cnt = 0;
        for (int i = x-1; i <= x+1; i++)
            for (int j = y-1; j <= y+1; j++)
                if (i >= 0 && i < board.size() && j >= 0 && j < board[0].size() && !(i==x && j==y))
                    cnt += board[i][j] % 10; // 只看個位（當前狀態）
        return cnt;
    }
};

// Java 版本 Runtime: 1 ms
public class Solution {
    public void gameOfLife(int[][] board) {
        int m = board.length, n = board[0].length;
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                int live = countLive(board, i, j);
                if (board[i][j] == 1 && (live == 2 || live == 3) ||
                    board[i][j] == 0 && live == 3)
                    board[i][j] += 10;
            }
        }
        for (int i = 0; i < m; i++)
            for (int j = 0; j < n; j++)
                board[i][j] /= 10;
    }
    private int countLive(int[][] board, int x, int y) {
        int cnt = 0;
        for (int i = x-1; i <= x+1; i++)
            for (int j = y-1; j <= y+1; j++)
                if (i >= 0 && i < m && j >= 0 && j < n && !(i==x && j==y))
                    cnt += board[i][j] % 10;
        return cnt;
    }
}

無限網格擴展思路

• 稀疏矩陣表示：只存活細胞坐標集合（HashSet/Map）
• 每輪只檢查活細胞及其鄰居（潛在變化區域）
• 邊界自然擴展，無固定大小限制

複雜度

• 時間：O(m×n) 每輪
• 空間：O(1) 額外（位編碼復用輸入數組）