C++刷LeetCode（289. 生命游戏）【数据结构】

糖逗

题目描述：

1. 根据 百度百科 ，生命游戏，简称为生命，是英国数学家约翰·何顿·康威在 1970 年发明的细胞自动机。
   
2. 
   
3. 给定一个包含 m × n 个格子的面板，每一个格子都可以看成是一个细胞。每个细胞都具有一个初始状态：1 即为活细胞（live），或 0 即为死细胞（dead）。每个细胞与其八个相邻位置（水平，垂直，对角线）的细胞都遵循以下四条生存定律：
   
4. 
   
5. 如果活细胞周围八个位置的活细胞数少于两个，则该位置活细胞死亡；
   
6. 如果活细胞周围八个位置有两个或三个活细胞，则该位置活细胞仍然存活；
   
7. 如果活细胞周围八个位置有超过三个活细胞，则该位置活细胞死亡；
   
8. 如果死细胞周围正好有三个活细胞，则该位置死细胞复活；
   
9. 根据当前状态，写一个函数来计算面板上所有细胞的下一个（一次更新后的）状态。下一个状态是通过将上述规则同时应用于当前状态下的每个细胞所形成的，其中细胞的出生和死亡是同时发生的。
   
10. 
    
11. 
    
12. 
    
13. 示例：
    
14. 
    
15. 输入：
    
16. [
    
17.   [0,1,0],
    
18.   [0,0,1],
    
19.   [1,1,1],
    
20.   [0,0,0]
    
21. ]
    
22. 输出：
    
23. [
    
24.   [0,0,0],
    
25.   [1,0,1],
    
26.   [0,1,1],
    
27.   [0,1,0]
    
28. ]
    
29. 
    
30. 
    
31. 进阶：
    
32. 
    
33. 你可以使用原地算法解决本题吗？请注意，面板上所有格子需要同时被更新：你不能先更新某些格子，然后使用它们的更新后的值再更新其他格子。
    
34. 本题中，我们使用二维数组来表示面板。原则上，面板是无限的，但当活细胞侵占了面板边界时会造成问题。你将如何解决这些问题？

复制代码

1. class Solution {
   
2. public:
   
3.     int around(int i , int j, vector<vector<int> >&board){
   
4.         int len1 = board.size(), len2 = board[0].size();
   
5.         int store = 0;
   
6.         if(j - 1 >= 0 &&board[i][j - 1] == 1) store++;//左
   
7.         if(j + 1 < len2 && board[i][j + 1] == 1) store++;//右
   
8.         if(i - 1 >= 0 && board[i - 1][j] == 1) store++;//上
   
9.         if(i + 1 < len1 && board[i + 1][j] == 1) store++;//下
   
10.         if((i - 1 >= 0 && j- 1 >= 0) && board[i-1][j-1] == 1)store++;//左上
    
11.         if((i - 1 >= 0&& j + 1< len2)&&board[i-1][j+1] == 1)store++;//右上
    
12.         if((i+1 < len1 && j + 1 < len2) && board[i+1][j+1] == 1)store++;//右下
    
13.         if((j - 1 >= 0 && i+1 < len1) && board[i+1][j-1] == 1)store++;//左下
    
14.         return store;
    
15.     }
    
16. 
    
17.     void gameOfLife(vector<vector<int>>& board) {
    
18.         int len1 = board.size(), len2 = board[0].size();
    
19.         vector<vector<int> > store;
    
20.         for(int i = 0; i < len1; i++){
    
21.             for(int j = 0; j < len2; j++){
    
22.                 int temp = around(i, j, board);
    
23.                 if(board[i][j] == 1 && temp < 2)store.push_back({i, j});
    
24.                 else if(board[i][j] == 1 && temp > 3)store.push_back({i, j});
    
25.                 else if(board[i][j] == 0 && temp == 3)store.push_back({i, j});
    
26.             }
    
27.         }
    
28.         for(int i = 0; i < store.size(); i++){//注意这一步要和上面单独分开
    
29.             if(board[store[i][0]][store[i][1]] == 1)board[store[i][0]][store[i][1]] = 0;
    
30.             else if(board[store[i][0]][store[i][1]] == 0){
    
31.                 board[store[i][0]][store[i][1]] = 1;
    
32.             }
    
33.         }
    
34.         return;
    
35.         
    
36.     }
    
37. };

复制代码

注意事项：1.编辑算边赋值会使得原来的形式变化，要分步进行。