LeetCode 每日一题 289. 生命游戏

2020.04.02
难度 中等

题目

根据 百度百科 ，生命游戏，简称为生命，是英国数学家约翰·何顿·康威在 1970 年发明的细胞自动机。
给定一个包含 m × n 个格子的面板，每一个格子都可以看成是一个细胞。每个细胞都具有一个初始状态：1 即为活细胞（live），或 0 即为死细胞（dead）。每个细胞与其八个相邻位置（水平，垂直，对角线）的细胞都遵循以下四条生存定律：

• 如果活细胞周围八个位置的活细胞数少于两个，则该位置活细胞死亡；
• 如果活细胞周围八个位置有两个或三个活细胞，则该位置活细胞仍然存活；
• 如果活细胞周围八个位置有超过三个活细胞，则该位置活细胞死亡；
• 如果死细胞周围正好有三个活细胞，则该位置死细胞复活；

根据当前状态，写一个函数来计算面板上所有细胞的下一个（一次更新后的）状态。下一个状态是通过将上述规则同时应用于当前状态下的每个细胞所形成的，其中细胞的出生和死亡是同时发生的。

示例：

输入：
[
[0,1,0],
[0,0,1],
[1,1,1],
[0,0,0]
]
输出：
[
[0,0,0],
[1,0,1],
[0,1,1],
[0,1,0]
]

题解

  这题让我们求解当前状态的下一个状态的值，并且出生和死亡是同时发生的，所以在这里我们不可以在原数据上直接进行修改，因为修改后的值会影响后面的判断。所以我们可以再复制一份数据，在复制出的数据上做判断，然后在原数据上进行修改，将判断和结果分开即可满足出生和死亡是同时发生的这个条件。然后我们遍历数据，求出每一次周围8个位置的活细胞数，然后进行相对应的操作即可。这里先放代码，代码中有详细的各个步骤的注解：

class Solution {
    //用来求当前位置的周围共有几个活细胞
    int getLive(int i,int j,vector<vector<int>> board){
        int ans = 0;
        //方向数组，左上、上、右上、右、右下、下、左下、左
        int dir[8][2] = {{-1,-1},{-1,0},{-1,1},{0,1},{1,1},{1,0},{1,-1},{0,-1}};
        //遍历8个方向
        for(int k = 0;k < 8; k++){
            // 赋值row,col，分别代表各个方向上的位置。
            int row = i + dir[k][0];
            int col = j + dir[k][1];
            // 如果board[row][col]在边界中，并且是活细胞，则ans++
            if(row >= 0 && row < board.size() && col >= 0 && col < board[row].size() && board[row][col] == 1){
                ans++;
            }
        }
        // 返回活细胞数量
        return ans;
    }
public:
    void gameOfLife(vector<vector<int>>& board) {
        int rows = board.size();
        int cols = board[0].size();
        //这里由于细胞的死亡和出生是同时进行的，即我们判断需要使用一开始的一个数据，所以我们这里新创建一个vector<vector<int>> copy;来记录原始的状态。
        vector<vector<int>> copy(rows,vector<int>(cols,0));
        //首先将board的原始状态赋值到ans
        for(int i = 0; i < rows; i++){
//            vector<int> mid;
            for(int j = 0; j < cols; j++){
                copy[i][j] = board[i][j];
//                mid.push_back(board[i][j]);
            }
//            copy.push_back(mid);
        }
        //下面开始处理这段数据
        for(int i = 0; i < rows; i++){
            for(int j = 0; j < cols; j++){
                //先找出周围一共有几个活细胞
                int num = getLive(i,j,copy);
                if(copy[i][j] == 1 && (num < 2 || num > 3)){
                    // 当copy[i][j] == 1时，即当前为活细胞时,并且num<2或则>3时，当前位置死亡，这时的修改只记录在board上，copy仅用作判断.
                    board[i][j] = 0;
                }
                if(copy[i][j] == 0 && num == 3){
                    //当前位置细胞为死亡，但是周围正好有3个活细胞时，死亡
                    board[i][j] = 1;
                }
            }
        }
    }
};