题目描述

给定一个矩阵，矩阵中每一个网格放了一个细胞，每一个细胞有两种状态，1为活细胞，0为死细胞，对于每个细胞都满足如下的条件：

1. 如果活细胞周围八个网格的活细胞数少于两个，则该网格活细胞死亡

2. 如果活细胞周围八个网格有两个或三个活细胞，则该网格活细胞仍然存活

3. 如果活细胞周围八个网格有超过三个活细胞，则该网格活细胞死亡

4. 如果死细胞周围正好有三个活细胞，则该网格死细胞复活

给出当前状态的矩阵，求下一状态的矩阵。题目要求必须在原始矩阵中操作，不能新建一个同样大小的数组矩阵。

样例

输入：  
[
  [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

（位操作）$O(mn)$

这题思路很简单，对每个位置按照题目所给规则进行遍历，判断周围网格的活细胞数即可。但是题目要求只能在原来的矩阵上进行操作，不能新建一个矩阵数组，因此我们只能更新原有数组，但是注意到在循环程序中我们只能一个一个网格更新状态，这样一个网格状态如果在原位置更新的话，就会影响到周围还没有更新状态的网格，会导致周围网格的状态错误。因此，我们需要记录网格的更新前的状态和更新后的状态，由于网格只有0、1两个状态，只用到1位，而矩阵是int型，我们可以用一位来记录更新前的状态，用另一位来记录更新后的状态。
在这题里，我们用最低位记录更新前的状态，用第二位来记录更新后的状态，例如$2={(10)}_2$表示更新前是0，更新后是1，$3={(11)_2}$表示更新前是1，更新后还是1，$1={(01)}_2$表示更新前是1，更新后是0。这样，我们可以通过位操作来节省空间，在原矩阵上进行操作即可。

需要遍历矩阵，因此时间复杂度为$O(mn)$，不需要额外矩阵空间，空间复杂度为$O(1)$

C++ 代码

class Solution {
public:
    void gameOfLife(vector<vector<int>>& board) {
        int m = board.size();
        if(m==0)
            return;
        int n = board[0].size();
        for(int i = 0;i < m;i++){
            for(int j = 0;j < n;j++){
                int neighbour = 0;//记录周围八个网格的活细胞数
                for(int di = -1;di <= 1; di++){
                    for(int dj = -1;dj <= 1;dj++){
                        if(i + di >=0 && i+di < m && j+dj >= 0 && j+dj < n &&!(di == 0 && dj == 0)){
                            neighbour += board[i+di][j+dj] & 1;//取每个网格的最低位（当前状态）
                        }
                    }
                }
                    if(board[i][j] == 1){
                        if(neighbour < 2 || neighbour > 3)
                            board[i][j] = 1;//更新后状态为0，所以记为01（二进制）
                        else
                            board[i][j] = 3;//更新后状态为1，所以记为11（二进制）
                    }
                    else{
                        if(neighbour == 3)
                            board[i][j]=2;//更新后状态为1，所以记为10（二进制）
                        else
                            board[i][j] = 0;//更新后状态为0，所以记为00（二进制）
                    }
                }
            }

        for(int i = 0;i<m;i++){
            for(int j = 0;j<n;j++){
                board[i][j] =(board[i][j]&2)>>1;//取每个网格的第二位，得到更新后状态
            }
        }
    }
};