289. Game of Life

According to the Wikipedia's article: "The Game of Life, also known simply as Life, is a cellular automaton devised by the British mathematician John Horton Conway in 1970."

Given a board with m by n cells, each cell has an initial state live (1) or dead (0). Each cell interacts with its eight neighbors (horizontal, vertical, diagonal) using the following four rules (taken from the above Wikipedia article):

Any live cell with fewer than two live neighbors dies, as if caused by under-population.
Any live cell with two or three live neighbors lives on to the next generation.
Any live cell with more than three live neighbors dies, as if by over-population..
Any dead cell with exactly three live neighbors becomes a live cell, as if by reproduction.
Write a function to compute the next state (after one update) of the board given its current state.

这里由于矩阵的只用了32位的最后一位来存储当前状态，此处使用倒数第二位来存储下一个状态。

循环遍历(i,j)周围的八个地方以及(i,j)的到周围的状态

活     周围活的状态<2          死
活     周围活的状态2<= <=3     活
活     周围活的状态>3          死
死     周围活的状态 =3         活


活下来的条件count,count记录它和它周围的八个点的状态
count == 3(对应于(1)它活，周围有两个活的(2)它死，它周围有三个活的)
count - board[i][j] == 3   （它活，周围有3个活的）

class Solution {
public:
    void gameOfLife(vector<vector<int>>& board) {
        int m = board.size(), n = m ? board[0].size() : 0;
        for (int i = 0; i < m; ++i) {
        for (int j = 0; j < n; ++j) {
            int count = 0;
            for (int I = max(i-1, 0); I < min(i+2, m); ++I)
                for (int J = max(j-1, 0); J < min(j+2, n); ++J)
                    count += board[I][J] & 1;
            //此处count中还包含(i, j)的状态
            /*if ((count | board[i][j]) == 3)*/
            if (count == 3 || count - board[i][j] == 3)
                board[i][j] |= 2;
        }
    }
    for (int i=0; i<m; ++i)
        for (int j=0; j<n; ++j)
            board[i][j] >>= 1;
    }
};