Game of Life

原題鏈接 Game of Life

生命游戲，計算下一個狀態。游戲規則如下

• 對于一個live的細胞，如果它周圍live的細胞數量少于兩個，那么它將dead
• 對于一個live的細胞，如果它周圍live的細胞數量是兩個或三個，那么它繼續live
• 對于一個live的細胞，如果它周圍live的細胞數量超過三個，那么它將dead
• 對于一個dead的細胞，如果它周圍live的細胞數量恰好是三個，那么它將live

給定某一時刻各個細胞的狀態，用二維數組表示，1表示live，0表示dead。需要返回下一個狀態，要求只能在原數組中更改，即空間復雜度在O(n)

不過有一點需要主要，每個細胞周圍有8個細胞，判斷這個細胞下一個狀態依據的是它周圍那么細胞的狀態。比說如當前狀態為A，下一個狀態為B。那么對于某個處于狀態A的細胞而言，要判斷它下一個狀態，依據的是它周圍8個細胞的A狀態，而不是B狀態。
這就要求不能一邊遍歷一邊修改，只能先遍歷一遍，記錄好哪些細胞需要改變狀態。然后在第二遍遍歷的時候更新狀態。

---

記錄的方式比較多，比如

增加幾個細胞的狀態，如2代表現在是live并且下一個狀態也是live；3代表現在是live但是下一個狀態是dead；4代表現在是dead但是下一個狀態是live

這樣，所有細胞當前的狀態和下一個狀態就都知道了，在第二次遍歷時，只需要根據2,3,4做適當的修改即可

代碼如下

class Solution { public:void gameOfLife(vector<vector<int>>& board) {//2 : current is live and next is live//3 : current is live but next is dead//4 : current is dead but next is liveif(board.empty() || board[0].empty())return;int m = board.size();int n = board[0].size();for(int i = 0; i < m; ++i){for(int j = 0; j < n; ++j){int liveCount = 0;/* 判斷周圍live的細胞數量 */for(int p = std::max(0, i - 1); p < std::min(m, i + 2); ++p){for(int q = std::max(0, j - 1); q < std::min(n, j + 2); ++q){if(p == i && q == j)continue;if(isLive(board, p, q))++liveCount;}}/* 根據周圍細胞數量改變狀態 */if(liveCount < 2 && isLive(board, i, j))board[i][j] = 3;else if(liveCount > 3 && isLive(board, i, j))board[i][j] = 3;else if(liveCount == 3 && !isLive(board, i, j))board[i][j] = 4;}}/* 第二次遍歷時改變狀態 */for(int i = 0; i < m; ++i){for(int j = 0; j < n; ++j){if(board[i][j] == 3)board[i][j] = 0;else if(board[i][j] == 4)board[i][j] = 1;}}}private:/* 一個細胞處于live的條件是當前狀態是live而不是下一個狀態是live */bool isLive(vector<vector<int>>& board, int i, int j){return board[i][j] == 1 || board[i][j] == 2 || board[i][j] == 3;} };

---

除了上面提到的增加細胞狀態的方法外，還有一種方法可以記錄細胞的當前狀態和下一個狀態。
因為最開始，細胞只有0和1兩種狀態，只需要一個字節即可記錄，也就是說int類型的其它位置實際上是用不上的。所以，可以將int類型其它字節用上，來記錄細胞的下一個狀態，不過只需要一個字節即可。

0和1的二進制碼分別是0000和0001，表示細胞處于dead狀態和live狀態。如果試圖將下一個狀態也記錄在這里面，就像

• 0000表示當前狀態是dead并且下一個狀態是dead，值為0
• 0010表示當前狀態是dead并且下一個狀態是live，值為2
• 0001表示當前狀態是live并且下一個狀態是dead，值為1
• 0011表示當前狀態是live并且下一個狀態是live，值為3

這樣，在第二遍遍歷時只需要將每個細胞的值右移一位，就從當前狀態變為下一個狀態了。

代碼如下

class Solution { public:void gameOfLife(vector<vector<int>>& board) {if(board.empty() || board[0].empty())return;int m = board.size();int n = board[0].size();for(int i = 0; i < m; ++i){for(int j = 0; j < n; ++j){int liveCount = 0;for(int p = std::max(0, i - 1); p < std::min(m, i + 2); ++p){for(int q = std::max(0, j - 1); q < std::min(n, j + 2); ++q){/* 這里沒有排除p == i && q == j */liveCount += (board[p][q] & 1);}}/* 對于live的細胞，它下一個狀態仍然是live的條件是算上它本身，周圍live的細胞數量是3或4個 *//* 對于dead的細胞，它下一個狀態是live的條件是算上它本身，周圍live的細胞數量是3個 *//* 不能直接liveCount == 4因為對于dead的細胞是錯誤的 */if(liveCount == 3 || liveCount - board[i][j] == 3)board[i][j] |= 2;}}for(int i = 0; i < m; ++i){for(int j = 0; j < n; ++j){board[i][j] >>= 1;}}} };

本題和每天一道LeetCode—–給定一個矩陣，如果某個元素是0，就將所在行所在列上所有元素否置0類似，都是在第一遍遍歷時在原二維數組上做記錄，在第二遍遍歷時集中更改。從而保證空間復雜度為O(1)，但是如何記錄，需要仔細考慮

總結

以上是生活随笔為你收集整理的每天一道LeetCode-----生命游戏的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。