4.4　生命游戲

題目描述（第289題）

生命游戲是英國數學家約翰·何頓·康威在1970年發明的細胞自動機。

給定一個包含mn個格子的面板，每個格子都可以被看成一個細胞。每個細胞具有一個初始狀態：live(1)，即活細胞；或dead(0)，即死細胞。每個細胞與其8個相鄰位置（水平、垂直、對角線）的細胞都遵循以下4條生存定律。

1.如果活細胞周圍8個位置的活細胞數少于2個，則該位置活細胞死亡。

2.如果活細胞周圍8個位置有2個或3個活細胞，則該位置活細胞仍然存活。

3.如果活細胞周圍8個位置有超過3個活細胞，則該位置活細胞死亡。

4.如果死細胞周圍正好有3個活細胞，則該位置死細胞復活。

根據當前狀態，寫一個函數來計算面板上細胞的下一個（一次更新后的）狀態。下一個狀態是通過將上述規則同時應用于當前狀態下的每個細胞所形成的，其中細胞的出生和死亡是同時發生的。

示例

輸入：

輸出：

進階

你可以使用原地算法解決本題嗎？請注意，面板上所有格子需要同時被更新：你不能先更新某些格子，然后使用它們的更新后的值再更新其他格子。

本題中，我們使用二維數組來表示面板。原則上，面板是無限的，但當活細胞侵占了面板邊界時會造成問題。你將如何解決這些問題？

背景

生命游戲乍看起來平淡無奇，游戲過程無人干預，細胞初始狀態和4條生存定律決定了之后的一切。然而恰恰在這樣簡單的設定之下，看似雜亂無序的細胞不斷誕生和消亡，逐漸演化出各種精致的結構形態；隨著時間的推移，有的結構會變得十分穩定，有的則規律地震蕩，還有的甚至會在空間中移動并與其他結構發生交互，儼然構成一副生命的圖景。

因為這些特點，生命游戲廣受計算機科學研究者的喜愛，大家爭相構建自己的生命系統，甚至有人用它構建圖靈機，大名鼎鼎的Emacs編輯器在很早的時期就內置了這個游戲。了解這些背景后你是否對本題興趣大增呢？讓我們看一看如何自己實現“生命”的演進吧。

思路

題目對具體場景和生存條件的描述非常清楚，因此實現思路也有章可循，根據題目分析實現的重點。

●　計算細胞鄰居個數，即8個相鄰位置存在的細胞數。

●　根據計算結果決定每個細胞的生死狀態，即0或1。

先來看一下細胞鄰居個數的計算。根據數組下標連續的特點，使用當前細胞的坐標值計算出鄰居細胞的位置獲取狀態，如當前細胞為board[i][j]，則其上邊的鄰居為board[i-1][j]，右邊的鄰居為board[i][j+1]；因為空間有限的設定，計算時需要注意邊界條件，當細胞處在空間邊緣、頂點位置時潛在鄰居的數目會小于8個。定義top、bottom、left、right 等4個變量對取值范圍進行預處理，當鄰居的坐標超出給定數組范圍時移動邊界。如下面的代碼所示。

得到鄰居細胞數量之后，我們要借助它判定并更新細胞的狀態。根據設定，在每輪游戲中，所有細胞要同時更新狀態，因此無法在一次遍歷中完成判定與更改，我們將這個過程分為兩個步驟。

●　遍歷所有細胞計算鄰居細胞的數量，根據生存法則判定并記錄下一回合對應的狀態。

●　狀態判定完成后，重新遍歷所有細胞依照記錄更新狀態。

基于上述分析，我們已經能夠進行基本的實現了，題目還有進階的條件限定，要求我們使用原地算法，這意味著在第一步不能使用額外的數組存放下一回合狀態的記錄。為避免在標記過程中使用1和0兩個狀態影響后續細胞的遍歷，約定使用-1表示當前回合為1且下一回合應變為0的狀態，使用-2表示當前回合為0且下一回合應變為1的狀態；相應地，在進行鄰居細胞計算時，遇到-1也認為當前該位細胞為存活狀態，雖然下一回就會死亡。

完成所有狀態的判定后，再進行一次遍歷，將-1和-2設置為0和1，這道題目就完美解決了。下面是基于上面思路實現的Python代碼。

代碼

復雜度分析

●　時間復雜度：由循環遍歷的方法可以得出時間復雜度為O(mn)，m和n分別為board數組的行數、列數。

●　空間復雜度：采用原地算法，空間復雜度為O(1)。