leetcode-每日一题-生命游戏(矩阵总结)

根据 百度百科 ，生命游戏，简称为生命，是英国数学家约翰·何顿·康威在 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]
]

题有点长，其实可以算是模拟，主要问题就是细胞状态的转变，这里可以在开一个数值来存，也就是原地算法；

所谓的原地算法：就是不依赖额外的资源或者依赖少数的额外资源，仅依靠输出来覆盖输入的一种算法操作。

class Solution {
public:
    void gameOfLife(vector<vector<int>>& board) {
        int n = board.size();
        int m = board[0].size();
        int dx[8] = {1,1,0,-1,-1,-1,0,1};
        int dy[8] = {0,1,1,1,0,-1,-1,-1};
        for(int i=0;i<n;i++){
            for(int j=0;j<m;j++){
                int x,y,live = 0;
                for(int ii = 0;ii<8;ii++){//往外遍历，找存活的
                    x = i+dx[ii];
                    y = j+dy[ii];
                    if(x>=n||x<0||y>=m||y<0) continue;
                    if(board[x][y]==1||board[x][y]==2) live++;
                }
                //模拟条件 存储的状态-1是死亡转生存，2是生存转死亡
                if(board[i][j]==0){
                    if(live==3){
                        board[i][j] = -1;
                    }
                }
                if(board[i][j]==1){
                    if(live<2) board[i][j] = 2;
                    if(live==2||live==3) board[i][j] = 1;
                    if(live>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] = 0;
                else if(board[i][j]==-1)
                    board[i][j] = 1;
            }
        }
    }
};

在看题解的时候发一个总结特别好的题解，这里引用一下qwq

总结：类似的矩阵问题有很多，但不管什么问题，有两个技巧是一定用的上的，一定要记住！！！

1、矩阵中某个位置的状态如果发生改变，那么这种题的解法一般是两次遍历整个矩阵。第一遍遍历时，用一个不可能出现在原矩阵中的中间值来保存状态的变化（这样在此次遍历时，不影响其他的位置的判断，比如我们可以用“$”这种没人用的字符）；第二遍遍历时，把中间值刷新成为变化后应该变成的值。

2、如果遍历到某个位置时，需要查看它周边的位置，此时如果每一个周围的位置都手写，然后再判断是否越界，就很麻烦。可以先用一个数组保存向周边位置变化的坐标偏移值，一次性通过一个循环，来遍历完周边的位置，并且方便进行越界判断。