LeetCode 289. Game of Life

Game of Life

题目
根据给出的四个条件，产生下一代的状态(live/die)
对于这道题很容易想到的就是记录每一个元素周围有几个live状态的元素，也就是有几个一，然后判断该元素的在下一个state中是死是活。但是肯定不可以判断完之后立刻就在同一个数组里改成下一个状态，这次更改会影响下一个元素的统计结果。那我们使用另外的数据空间（可以是另一个数组），记录下来新的状态。这是基本的思路。
但这道题的follow up要求用in-place 而不是使用另外的数组。这道题有一个非常有趣的点是 本来可以用boolean就可以表示的生命状态用了int，如下

live: 0 0 0 0 0 0 0 1
die: 0 0 0 0 0 0 0 0

既然如此，我们可以用这个int的倒数第二位来记录下一个的状态(current_element |= 2)，然后在记录完所有的元素之后，用另外一次遍历让所有的元素右移一位，便得到了最终的结果(current_element >>= 1)。
不过要注意的是，这个方法不仅统计了当前元素的邻居，而且把自己也算进去了。做count -= current_element 才能得出邻居

class Solution {
public:
    void gameOfLife(vector<vector<int>>& board) {
        int row(board.size()), column(board[0].size());
        for (int i = 0; i < row; i++) {
            for (int j = 0; j < column; j++) {
                int count = 0;
                for (int I = max(i - 1, 0); I < min(i + 2, row); I++)
                    for (int J = max(j - 1, 0); J < min(j + 2, column); J++)
                        count += board[I][J] & 1;
                if (count == 3 || (count == 2 && board[i][j]))
                    board[i][j] |= 2;
            }
        }
        for (int i = 0; i < row; i++)
            for (int j = 0; j < column; j++)
                board[i][j] >>= 1;
    }
};