leetcode面试经典150题——38 生命游戏

题目：生命游戏

**描述：**根据 百度百科 ， 生命游戏 ，简称为 生命 ，是英国数学家约翰·何顿·康威在 1970 年发明的细胞自动机。

给定一个包含 m × n 个格子的面板，每一个格子都可以看成是一个细胞。每个细胞都具有一个初始状态： 1 即为 活细胞 （live），或 0 即为 死细胞 （dead）。每个细胞与其八个相邻位置（水平，垂直，对角线）的细胞都遵循以下四条生存定律：

1.如果活细胞周围八个位置的活细胞数少于两个，则该位置活细胞死亡；
2.如果活细胞周围八个位置有两个或三个活细胞，则该位置活细胞仍然存活；
3.如果活细胞周围八个位置有超过三个活细胞，则该位置活细胞死亡；
4.如果死细胞周围正好有三个活细胞，则该位置死细胞复活；
下一个状态是通过将上述规则同时应用于当前状态下的每个细胞所形成的，其中细胞的出生和死亡是同时发生的。给你 m x n 网格面板 board 的当前状态，返回下一个状态。
leetcode链接

输入：board = [[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个细胞活细胞的数量，按照题目所设条件，如果活细胞的数量大于3个或者小于2个，那么该活细胞变死细胞，如果活细胞的数量为3个，那么该死细胞变为活细胞，为了避免我们使用到更新后的细胞状态，我们把更新后的细胞状态存储到我们定义的新的矩阵中。
时间复杂度：o（mn）
空间复杂度：o（mn）

 void gameOfLife(vector<vector<int>>& board) {
    int n = board.size();
    int m = board[0].size();
    vector<vector<int> > new_board = board;
    for(int i=0;i<n;i++){
        for(int j=0;j<m;j++){
            int hnums = count(board,i,j);
            if((hnums<2||hnums>3)&&board[i][j]==1){
                //周围活细胞小于2个或者大于3个，该活细胞变成死细胞
                new_board[i][j] = 0;
            }else if(hnums==3&&board[i][j]==0){
                //周围活细胞数量为3个，该死细胞复活
                new_board[i][j] = 1;
            }        }
    }
    board = new_board;//最后复制为原矩阵中
}
int count(vector<vector<int> > nums,int row,int col){
    int hnums = 0;;
    for(int i = row-1;i<row+2;i++){
        for(int j =col-1;j<col+2;j++){
            if(i>=0&&j>=0&&i<nums.size()&&j<nums[0].size()&&nums[i][j]==1){
                hnums++;
            }
        }
    }
    return nums[row][col]==1?hnums-1:hnums;
}

方法二：使用额外的状态
在方法一中我们算法的时间复杂度为o(mn)，我们现在考虑原地解决该问题，在方法一中，如果我们步额外申请矩阵来存储，那么我们对于更新后的细胞状态，在后续使用时，会丢失掉原本最初的细胞状态，因此会得到错误的结果，那么我们要怎么样在既得到变化后的状态又能够得到最初的状态呢，我们为了解决这个问题，引入额外的两种状态-1和2，第一种-1状态表示细胞原本是活细胞，更新后变为死细胞，第二种2状态表示细胞原本是死细胞，更新后变为活细胞，那么我们在统计活细胞的时候，状态1和-1都表示原本是活细胞，这样就能解决既得到变化后的状态又能够得到最初的状态，最后我们只需要对我们新引入的状态对其还原即可。
时间复杂度：o(mn)
空间复杂度：o(1)

void gameOfLife(vector<vector<int>>& board) {
    int n = board.size();
    int m = board[0].size();
    for(int i=0;i<n;i++){
        for(int j=0;j<m;j++){
            int livenums = count(board,i,j);//周围活细胞的数量
            if((livenums>3||livenums<2)&&board[i][j]==1){
                //周围活细胞数量超过三个或者少于两个，该活细胞变成死细胞
                board[i][j] = -1;
            }else if(livenums==3&&board[i][j]==0){
                //周围活细胞的数量为3个，那么该死细胞变成活细胞
                board[i][j] = 2;
            }
        }
    }
    //最后把我们新定义的状态恢复
    for(int i=0;i<n;i++){
        for(int j=0;j<m;j++){
            if(board[i][j]==2){
                board[i][j] = 1;
            }else if(board[i][j]==-1){
                board[i][j] = 0;
            }
        }
    }
}
//统计活细胞的数量
int count(vector<vector<int> > nums,int row,int col){
    int hnums = 0;;
    for(int i = row-1;i<row+2;i++){
        for(int j =col-1;j<col+2;j++){
            if(i>=0&&j>=0&&i<nums.size()&&j<nums[0].size()&&(nums[i][j]==1||nums[i][j]==-1)){
                //原本是活细胞的值可能是1或者-1
                hnums++;
            }
        }
    }
    return nums[row][col]==1?hnums-1:hnums;
}