题目描述 生命游戏

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

给定一个包含 m × n 个格子的面板，每一个格子都可以看成是一个细胞。每个细胞具有一个初始状态 live（1）即为活细胞， 或 dead（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]]
进阶:
你可以使用原地算法解决本题吗？请注意，面板上所有格子需要同时被更新：你不能先更新某些格子，然后使用它们的更新后的值再更新其他格子。
本题中，我们使用二维数组来表示面板。原则上，面板是无限的，但当活细胞侵占了面板边界时会造成问题。你将如何解决这些问题？

解题思路

• 矩阵的元素是同时改变的，也就是说不能用更新后的元素进行计算，但是原地算法又不能使用额外的空间存储更新后的元素。所以想到先遍历一遍将活得节点坐标存在hashset里面。
• 然后再遍历一遍，计算这个节点8个点有几个为1。到hashset里面找就好啦。

来，上次说过了，写好代码要优化，虽然我这个菜鸡优化不来，但是要看看大神们怎么写的，看着看着可能就会了呢~ 万一会了呢~ 对吧。

大神思想来了
参考
矩阵的元素是同时改变的，也就是说不能用更新后的元素进行计算，但是原地算法又不能使用额外的空间存储更新后的元素，所以想到了用原矩阵同时保存原始数据和新数据。怎么样，是不是一听就不一样，关键咋不一样呢？

• 为了同时保存两个数据，那么原来的0和1两个变量就不能满足要求了，由于一共有四种可能，活-活，活-死，死-活，死-死。所以使用四个标识符来记录信息
• 遍历一遍计算周围活细胞数量，并且将活-死用2表示，死-活用-1表示。
• 最后遍历一次矩阵后把所有2改成0，-1改成1。
  嗯，大神果然不一样，我的脑子大概是少根茎把......

菜鸡代码

class Solution {
public:
    void gameOfLife(vector<vector<int>>& board) {
        if(board.empty() || board[0].empty()) return;
        set<pair<int,int>> hashset;
        for(int i=0;i<board.size();i++){
            for(int j=0;j<board[0].size();j++){
                if(board[i][j]==1)
                    hashset.insert(make_pair(i, j));
            }
        }
        vector<int> x={0, 0, -1, -1, 1, 1, -1, 1};
        vector<int> y={-1, 1, -1, 1, -1, 1, 0, 0};
        for(int i=0;i<board.size();i++){
            for(int j=0;j<board[0].size();j++){
                int num=0;
                for(int k=0;k<8;k++){
                    if(hashset.count(make_pair(i+x[k],j+y[k]))>0) num++;
                }
                if(num<2) board[i][j] = 0;
                else if(num==3) board[i][j] = 1;
                else if(num>3) board[i][j] = 0;

            }
        }
    }
};

大神代码

class Solution {
public:
    void gameOfLife(vector<vector<int>>& board) 
    {
        for(int i=0;i<board.size();i++)
            for(int j=0;j<board[0].size();j++)
                neiour(board,i,j);
        for(int i=0;i<board.size();i++)
            for(int j=0;j<board[0].size();j++)
            {
                if(board[i][j] == 2)
                    board[i][j] = 0;
                if(board[i][j] == -1)
                    board[i][j] = 1;
            }

    }
    void neiour(vector<vector<int>>& board,int x,int y)
    {
        int live = 0;
        if(x>0)
        {
            if(board[x-1][y]>0)
                live++;
            if(y>0 && board[x-1][y-1]>0)
                live++;
            if(y<board[0].size()-1 && board[x-1][y+1]>0)
                live++; 
        }
        if(x<board.size()-1)
        {
            if(board[x+1][y]>0)
                live++;
            if(y>0 && board[x+1][y-1]>0)
                live++;
            if(y<board[0].size()-1 && board[x+1][y+1]>0)
                live++; 
        }
        if(y >0 && board[x][y-1]>0)
            live++;
        if(y < board[0].size()-1 && board[x][y+1]>0)
            live++;
        if(board[x][y] == 1)
        {
            if(live<2||live>3)
                board[x][y] = 2;
        }
        else if(live == 3)
            board[x][y] = -1;
    }
};