289. Game of Life

According to theWikipedia'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 aboard 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):

1. Any live cell with fewer than two live neighbors dies, as if caused by under-population.
2. Any live cell with two or three live neighbors lives on to the next generation.
3. Any live cell with more than three live neighbors dies, as if by over-population..
4. 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.

Follow up:

1. Could you solve it in-place? Remember that the board needs to be updated at the same time: You cannot update some cells first and then use their updated values to update other cells.
2. In this question, we represent the board using a 2D array. In principle, the board is infinite, which would cause problems when the active area encroaches the border of the array. How would you address these problems?

S：bit manipulation O(mn)

board只用了最后一个bit，要in-place的话可以利用倒数第二位存储更新后的结果，最后右移一位

    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 count = -board[i][j];
                for (int r = max(0, i - 1); r <= min(m - 1, i + 1); ++r) {
                    for (int c = max(0, j - 1); c <= min(n - 1, j + 1); ++c) {
                        count += board[r][c] & 1;
                    }
                }              
                if ((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;
            }
        }