leetcode之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 aboard withm byn cells, each cell has an initial statelive (1) ordead (0). Each cell interacts with itseight 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?
问题来源：Game of Life (详细地址:https://leetcode.com/problems/game-of-life/#/description)
思路：这道题的比较符合实际场景，所以第一次见到的话可能会有点懵逼，完全不知道咋搞啊。下面简单翻译一下游戏规则(只翻译主要意思，不一字一句来了)：
1.一个活的细胞如果它的邻居当中活着的少于两个的话，则它自己也会死；
2.一个活的细胞如果它的邻居当中活着的有两个或者三个的话，则它也能继续活下去；
3.一个活的细胞如果它的邻居当中活着的超过了三个的话,则它自己也会死；
4.一个死的细胞如果它的邻居当中活着的有三个的话，则它会复活。
一开始我也完全不知道咋解决，最后在discuss中找到了解决方案(discuss原文地址 ) ,在这我只是负责翻译一下，然后再加上点自己的理解：
在这，它采用两bit来记录当前状态和下一个状态，总共无非就是四种情况嘛，具体状态描述如下：
[第二位， 第一位] = [下一状态， 当前状态]
00 ：下一状态是0，当前状态也是0，即死(当前状态) -> 死(下一状态)；
01 ：下一状态是0，当前状态是1，即活(当前状态) -> 死(下一状态)；
10 ：下一状态是1，当前状态是0，即死(当前状态) -> 活(下一状态)；
11 ：下一状态是1，当前状态是1，即活(当前状态) -> 活(下一状态)。
下面介绍已知条件和问题特点：
1）刚开始的时候，每个细胞要么是死要么是活，所以状态就只有可能是00或者是01；
2）第一个状态和第二个状态之间是相互独立的；
3）每个细胞从当前状态转化为下一状态都是同时进行的，并不会互相干扰；
4）由于每个细胞的第二位状态(下一状态)刚开始都是0，所以只需要考虑啥时候第二位状态变成了1，即可以不用考虑01 -> 00的状态变化；
5）最后，题目需要求下一状态，即第二位状态，所以只需要向右移动一位即可(采用 >> 1就可以了)。
接下来考虑状态何时变化，如何转变为if语句：
1)当前是活的状态，而且它的邻居中有两个或者三个是活的，那么它接下来还是活的，转化为if语句就是(假设board就是上文提到的2D数组)：
if(board[i][j] == 1 && lives >= 2 && lives <= 3)
board[i][j] = 3(因为变成了11，转化为十进制就是3)；
2)当前是死的状态，而且它的邻居中有三个是活的，那么它可以起死回生变成活的，转化为if语句就是：
if(board[i][j] == 0 && lives = 3)
board[i][j] = 2(理由和上面是一样的)；
知道了状态变化情况，总感觉还少了点啥，好像我们还不知道咋求当前状态和下一状态诶(下一状态其实上文已经给出了)：
当前状态如何求：board[i][j] & 1
下一状态如何求：board[i][j] >> 1
该讲的好像也讲的差不多了，其他的就是一些细节上面的东西了，比如控制数组边界情况等，其他的就在代码中给出好了。
代码：
下面就是求八个邻居结点中，状态是活着的结点个数：
体会：最大的体会就是这道题的规则比较多，如何转化为我们熟悉的问题，这是这道题最难的地方之一吧，另外，还需要根据游戏规则求出状态是如何变化的。