?

一、題目描述

根據百度百科，生命游戲，簡稱為生命，是英國數學家約翰·何頓·康威在1970年發明的細胞自動機。

給定一個包含 m × n 個格子的面板，每一個格子都可以看成是一個細胞。每個細胞具有一個初始狀態?live（1）即為活細胞， 或?dead（0）即為死細胞。每個細胞與其八個相鄰位置（水平，垂直，對角線）的細胞都遵循以下四條生存定律：

如果活細胞周圍八個位置的活細胞數少于兩個，則該位置活細胞死亡；

如果活細胞周圍八個位置有兩個或三個活細胞，則該位置活細胞仍然存活；

如果活細胞周圍八個位置有超過三個活細胞，則該位置活細胞死亡；

如果死細胞周圍正好有三個活細胞，則該位置死細胞復活；

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

示例:

輸入: [[0,1,0],[0,0,1],[1,1,1],[0,0,0] ] 輸出: [[0,0,0],[1,0,1],[0,1,1],[0,1,0] ]

二、題目解析

//根據矩陣的前一狀態更新下一個狀態，原地變換
//將原來是1，現在是0的位置用2標記；原來是0，現在是1的位置用3標記
//那么檢查幾個方向，如果是1或者2，代表這個位置原來是1；如果是0或者3，代表這個位置原來是0
//最后將所有的2換為0，將所有的3換為1即可
//判斷前后左右上下的方法，采用循環。——注意判斷面板邊界

三、代碼實現

1 class Solution { 2 public: 3 void gameOfLife(vector<vector<int>>& board) { 4 int m = board.size(); 5 if (!m)return; 6 int n = board[0].size(); 7 if (!n)return; 8 int live_cnt; 9 for (int i = 0; i < m; ++i) { 10 live_cnt = 0; 11 for (int j = 0; j < n; ++j) { 12 live_cnt = getLive(i, j, board); 13 if (board[i][j] == 0 && live_cnt == 3)board[i][j] = 3; 14 else if (board[i][j] == 1) { 15 --live_cnt;//包含自身 16 if (live_cnt < 2 || live_cnt>3) 17 board[i][j] = 2; 18 } 19 } 20 } 21 for (int i = 0; i < m; ++i) { 22 for (int j = 0; j < n; ++j) { 23 if (board[i][j] == 2) 24 board[i][j] = 0; 25 else if (board[i][j] == 3) 26 board[i][j] = 1; 27 } 28 } 29 } 30 private: 31 int getLive(int row, int col, vector<vector<int>> &board) { 32 int live_cnt = 0; 33 int m = board.size(), n = board[row].size(); 34 for (int i = max(0, row - 1); i < min(m, row + 2); ++i) { 35 for (int j = max(0, col - 1); j < min(n, col + 2); ++j) { 36 if (board[i][j] == 1 || board[i][j] == 2) 37 ++live_cnt; 38 } 39 } 40 return live_cnt; 41 } 42 };

?

轉載于:https://www.cnblogs.com/zhizhiyu/p/10173172.html

總結

以上是生活随笔為你收集整理的[Leetcode] 第289题 生命游戏的全部內容，希望文章能夠幫你解決所遇到的問題。

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