289. Game of Life

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;
                }
            }
        }
    }
};

• T: $O(M \cdot N)$
• S: $O(1)$