289. Game of Life

「生命遊戲」是一個細胞自動機的模擬問題。以下是這題的主要內容:

1. 給定一個 m x n 的二維整數陣列 board,代表細胞的狀態。
2. 每個細胞有兩種狀態:活(1)或死(0)。
3. 每個細胞與其周圍八個相鄰細胞互動。

規則如下:

• 活細胞周圍活細胞少於 2 個,因孤單而死。
• 活細胞周圍有 2 或 3 個活細胞,保持活。
• 活細胞周圍超過 3 個活細胞,因人口過剩而死。
• 死細胞周圍正好有 3 個活細胞,則復活。

任務是:計算所有細胞同時應用規則後的下一個狀態。

解題關鍵:

1. 原地更新陣列,不使用額外空間。
2. 同時更新所有細胞狀態,不能讓更新的細胞影響其他細胞的判斷。

一個常見的解法是使用狀態編碼:

• 用 2 表示由死變活
• 用 3 表示由活變死

這樣可以在原陣列中同時保存舊狀態和新狀態的信息。

Solution

class Solution {
public:
    void gameOfLife(vector<vector<int>>& board)
    {
        int m = board.size(), n = board[0].size();
        
        // 狀態：
        // 0 -> 目前死的細胞
        // 1 -> 目前活的細胞
        // 2 -> 目前活的，但即將死亡的細胞
        // 3 -> 目前死的，但即將復活的細胞
        
        // 周圍八個格子
        vector<vector<int>> directions = {{-1, -1}, {-1, 0}, {-1, 1}, {0, 1}, {1, 1}, {1, 0}, {1, -1}, {0, -1}};
        
        for (int i = 0; i < m; ++i)
        {
            for (int j = 0; j < n; ++j)
            {
                // 計算活細胞的數量
                int cnt = 0;

                // 走訪目標格子的周圍八個格子
                for (int k = 0; k < 8; ++k)
                {
                    // 新的 x, y
                    int x = i + directions[k][0], y = j + directions[k][1];

                    // 計算活細胞（值為1或2）的數量並存儲在 cnt 中。
                    if (x >= 0 && x < m && y >= 0 && y < n && (board[x][y] == 1 || board[x][y] == 2))
                    {
                        ++cnt;
                    }
                }

                // 如果細胞目前是活的（board[i][j] == 1）且活鄰居數少於2或多於3，則該細胞將變為死（標記為2）。
                if (board[i][j] && (cnt < 2 || cnt > 3))
                {
                    board[i][j] = 2;
                }
                // 如果細胞目前是死的（board[i][j] == 0）且有正好3個活鄰居，則該細胞將變為活（標記為3）。
                else if (!board[i][j] && cnt == 3)
                {
                    board[i][j] = 3;
                }
            }
        }

        for (int i = 0; i < m; ++i)
        {
            for (int j = 0; j < n; ++j)
            {
                // 標記為2的細胞（原本活的，但應變為死的）會被設置為0。
                if (board[i][j] == 2)
                {
                    board[i][j] = 0;
                }
                // 標記為3的細胞（原本死的，但應變為活的）會被設置為1。
                else if (board[i][j] == 3)
                {
                    board[i][j] = 1;
                }
            }
        }
    }
};

• 時間複雜度：
  $O(m\cdot n)$
• 空間複雜度：
  $O(1)$