According to the : "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  (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?

class Solution {public:    void gameOfLife(vector
     
      
       >& board) {        int m = board.size();        if(m <= 0)            return;        int n = board[0].size(), i, j, k;        int dir[8][2] = {
   {-1,-1},{
   0,-1},{
   1,-1},{-1,0},{
   1,0},{-1,1},{
   0,1},{
   1,1}};        for(i = 0; i < m; i++)        {            for(j = 0; j < n; j++)            {                int cnt = 0;                for(k = 0; k < 8; k++)                {                    int x = i + dir[k][0], y = j + dir[k][1];                    if(x >= 0 && x < m && y >= 0 && y < n && (1 == board[x][y] || 2 == board[x][y]))                        cnt++;                }                if(0 == board[i][j] && 3 == cnt)                    board[i][j] = 3;                else if(1 == board[i][j] && !(2 == cnt || 3 == cnt))                    board[i][j] = 2;            }        }        for(i = 0; i < m; i++)        {            for(j = 0; j < n; j++)                board[i][j] %= 2;        }    }};
      
     

由于题目中要求我们用in-place置换方法来解题，所以我们就不能新建一个相同大小的数组，那么只能更新原有数组，但是题目中要求所有的位置必须被同时更新，但是在循环程序中我们还是一个位置一个位置更新的，那么当一个位置更新了，这个位置成为其他位置的neighbor时，我们怎么知道其未更新的状态呢，我们可以使用状态机转换：

状态0： 死细胞转为死细胞

状态1： 活细胞转为活细胞

状态2： 活细胞转为死细胞

状态3： 死细胞转为活细胞

最后我们对所有状态对2取余，那么状态0和2就变成死细胞，状态1和3就是活细胞，达成目的。我们先对原数组进行逐个扫描，对于每一个位置，扫描其周围八个位置，如果遇到状态1或2，就计数器累加1，扫完8个邻居，如果少于两个活细胞或者大于三个活细胞，而且当前位置是活细胞的话，标记状态2，如果正好有三个活细胞且当前是死细胞的话，标记状态3。完成一遍扫描后再对数据扫描一遍，对2取余变成我们想要的结果。

http://www.cnblogs.com/grandyang/p/4854466.html