Leetcode

289 Game of Life

題目連結

289 Game of Life

題目說明

這道題目是一個模擬遊戲，稱為康威生命遊戲（Conway’s Game of Life）。遊戲的主要元素是一個由細胞組成的網格，每個細胞可以是活著的（用1表示）或死亡的（用0表示）。

遊戲的規則非常簡單，每個細胞與其周圍的八個鄰居（水平、垂直和對角線方向）進行交互作用，根據以下四條規則來決定下一個時刻的狀態：

  1. 如果一個活細胞周圍的活細胞少於兩個，則該細胞會因為人口不足而死亡。
  2. 如果一個活細胞周圍有兩個或三個活細胞，則該細胞在下一代中繼續存活。
  3. 如果一個活細胞周圍的活細胞超過三個，則該細胞會因為人口過剩而死亡。
  4. 如果一個死細胞周圍正好有三個活細胞，則該細胞會因為繁殖而成為活細胞。

下一個時刻的網格狀態是通過同時應用上述規則到當前時刻的每個細胞上來生成的，出生和死亡是同時發生的。題目給定了當前網格的狀態 board，要求返回下一個時刻的狀態。

換句話說，你需要根據上述規則對 board 中的每個細胞進行計算，並根據規則更新其狀態。最終返回更新後的網格狀態。

解題思路

首先解釋一下生命遊戲的規則。生命遊戲在一個二維格子中進行，每一個格子代表一個生命體，這個生命體有兩種狀態：生(1)和死(0)。
每個生命體的生死由其周圍八個格子的生命體狀態決定，規則如下：

  1. 如果一個生命體周圍有少於2個生命體，該生命體在下一輪會死亡。
  2. 如果一個生命體周圍有2個或3個生命體，該生命體在下一輪會保持當前狀態。
  3. 如果一個生命體周圍有超過3個生命體，該生命體在下一輪會死亡。
  4. 如果一個死亡的生命體周圍有正好3個生命體，該生命體在下一輪會復活。

程式碼中的gameOfLife方法用來進行一次遊戲的迭代。
它首先遍歷每一個生命體，並對其周圍的生命體進行計數(countLive方法用來計算周圍的生命體數量)。
根據計數的結果，然後決定每一個生命體在下一輪的狀態。

為了避免在計數過程中被即時更新的狀態影響，
這個方法選擇了一種巧妙的方式，使用兩個中間狀態：live(3)代表從死亡狀態變為生存，die(2)代表從生存狀態變為死亡。
這種方式可以讓我們在遍歷並更新狀態時，仍然可以正確計數周圍原來的生命體數量。

在完成狀態更新後，程式碼再次遍歷每一個生命體，將之前設置的中間狀態轉換回最終的生或死狀態。

這樣，我們就完成了生命遊戲的一次迭代。

實作


/**
 * @param {number[][]} board
 * @return {void} Do not return anything, modify board in-place instead.
 */

let die = 2;
let live = 3;

var gameOfLife = function (board) {

    let rowslength = board.length;
    let colsLength = board[0].length;

    for (let r = 0; r < rowslength; r++) {
        for (let c = 0; c < colsLength; c++) {

            // 開始計算每一個 cell 未來是活細胞還是死細胞
            let aroundLives = countAroundLives(board, r, c);

            /**
                1. 如果一個活細胞周圍的活細胞少於兩個，則該細胞會因為人口不足而死亡。
                2. 如果一個活細胞周圍有兩個或三個活細胞，則該細胞在下一代中繼續存活。
                3. 如果一個活細胞周圍的活細胞超過三個，則該細胞會因為人口過剩而死亡。
                4. 如果一個死細胞周圍正好有三個活細胞，則該細胞會因為繁殖而成為活細胞。
            */
            if (board[r][c] == 1 && (aroundLives < 2 || aroundLives > 3)) {
                board[r][c] = die;
            } else if (board[r][c] == 1 && (aroundLives == 2 || aroundLives == 3)) {
                // console.log("Nothing to do.");
            } else if (board[r][c] == 0 && aroundLives == 3) {
                board[r][c] = live;
            }

        }

    }


    // 再來將 die / live 各轉為 0 / 1
    for (let x = 0; x < board.length; x++) {
        for (let y = 0; y < board[0].length; y++) {
            if (board[x][y] == die) {
                board[x][y] = 0;
            } else if (board[x][y] == live) {
                board[x][y] = 1;
            }
        }
    }

};

let countAroundLives = function (board, r, c) {
    // 假設 board[r][c] 為中心點，設定為 (0, 0)，周圍會有以下的位置：
    let aroundLocations = [[1, 0], [1, 1], [0, 1], [-1, 1], [-1, 0], [-1, -1], [0, -1], [1, - 1]];

    let count = 0;

    for (let i = 0; i < aroundLocations.length; i++) {
        let location = aroundLocations[i];
        let x = location[0];
        let y = location[1];

        // 超過邊界範圍，因為 2D array 的位置不可能為負數
        if ((x + r) < 0 || (c + y) < 0) {
            continue;
        } else if ((x + r) >= board.length || (c + y) >= board[0].length) {
            continue;
        } else if (board[x + r][c + y] == 1 || board[x + r][c + y] == die) {
            count++;
        }

    }

    return count;
}

/** 
 *    board:
 *      3
 *    /   \
 *    0 1 0 \   
 *    0 0 1   
 *    1 1 1   4   
 *    0 0 0 /
 * 
 *    expect result:
 *    0 0 0                  
 *    1 0 1                  
 *    0 1 1                  
 *    0 1 0                  
 */
let board = [[0, 1, 0], [0, 0, 1], [1, 1, 1], [0, 0, 0]];
let gameOfLifeResult = gameOfLife(board);
console.log(gameOfLifeResult);

最後，如果你覺得我的分享對你有幫助，請給予我一個愛心，並且分享這篇文章，這將是對我最大的鼓勵！