Game of Life

lc 289

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.

解题报告：这个题目可以用位运算的思路，这个题目一开始理解的时候握理解错了，题目要求同时更新的意思是更新就一块更新了，这样的不会因为某一点更新造成其他点没法运算。而number of island是某一点更新了，会对邻近点造成影响的。其实理解了题目就比较简单了，可以用2位来表示状态

第二位，第一位， 第一位表示current state 第二位表示next state 我们可以创建一个计算有多少个邻居的helper函数，然后更新这个位置数字的第二位。当便利万一边以后，集中右移一位，将next更改成当前状态。

https://discuss.leetcode.com/topic/29054/easiest-java-solution-with-explanation/2

public class Solution {
    public void gameOfLife(int[][] board) {
        if(board == null || board.length == 0) return;
        int m = board.length;
        int n = board[0].length;
        for(int i = 0; i < m; i++){
            for(int j = 0; j < n; j++){
                //count live neibours
                int lives = liveNeighbors(board, i, j);
                //dead -> live
                if(lives == 3 && (board[i][j] & 1) == 0){
                    board[i][j] |= (1 << 1);
                    //board[i][j] = 2;
                }else if( (board[i][j] & 1) == 1 && lives >= 2 && lives <=3  ){
                    board[i][j] |= (1 << 1);
                    //board[i][j] = 3;
                }
            }
        }

        for(int i = 0; i < m; i++) {
            for(int j = 0; j < n; j++) {
                board[i][j] >>= 1;  // Get the 2nd state.
            }
        }
    }

    public int liveNeighbors(int[][] board, int i, int j){
        int lives = 0;
        for(int x = Math.max(i - 1, 0); x <= Math.min(i + 1, board.length - 1); x++){
            for(int y = Math.max(j - 1, 0); y <= Math.min(j + 1, board[0].length - 1); y++) {
                lives += board[x][y] & 1;

            }
        }
        lives -= board[i][j] & 1;
        return lives;
    }
}