# 【LeetCode】 289. Game of Life

## Description
> 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. The next state is created by applying the above rules simultaneously to every cell in the current state, where births and deaths occur simultaneously.

> 根據維基百科的文章：『生命遊戲，也有人簡稱生命，是一種細胞自動機，在1970年被英國數學家John Horton Conway設計出來的。』
> 給予一個m*n棋盤狀的細胞格，每一格之中只會有0或1代表該細胞是存活或死亡。每個細胞會與周遭八宮格的其他細胞(稱作他的"鄰居")互動，其互動根據以下四種規則(參考維基百科)：
> - 當前細胞為存活狀態時，當周圍的存活細胞低於2個時（不包含2個），該細胞變成死亡狀態。（模擬生命數量稀少）
> - 當前細胞為存活狀態時，當周圍有2個或3個存活細胞時，該細胞保持原樣。
> - 當前細胞為存活狀態時，當周圍有超過3個存活細胞時，該細胞變成死亡狀態。（模擬生命數量過多）
> - 當前細胞為死亡狀態時，當周圍有3個存活細胞時，該細胞變成存活狀態。（模擬繁殖）

> 請寫一個函式，將給予的棋盤更新至下一個狀態。其死亡或誕生完全參考至上方的規則去進行模擬。

## Example:

Input: 
[
  [0,1,0],
  [0,0,1],
  [1,1,1],
  [0,0,0]
]
Output: 
[
  [0,0,0],
  [1,0,1],
  [0,1,1],
  [0,1,0]
]

## Solution

* 思考：如何限制在in-place的情況來完成。
* 用二進制去想，一位表示現在狀態，二位表示下一個狀態。
* 00代表現在死亡，下一步也死亡。
* 01代表現在存活，下一步死亡。
* 10代表現在死亡，下一步誕生。
* 11代表現在存活，下一步也存活。
* 思考：如何避免邊界問題。
* 硬爆，大量判斷。

### Code

class Solution {
public:
    
    int getAliveNeighbors(vector<vector<int>>& board,int x,int y)
    {
        int count = 0;
        if(y!=0&&x!=0)
            count += board[y-1][x-1]&1;
        if(x!=0)
            count += board[y][x-1]&1;
        if(y!=board.size()-1&&x!=0)
            count += board[y+1][x-1]&1;
        if(y!=0)
            count += board[y-1][x]&1;
        if(y!=board.size()-1)
            count += board[y+1][x]&1;
        if(y!=0&&x!=board[0].size()-1)
            count += board[y-1][x+1]&1;
        if(x!=board[0].size()-1)
            count += board[y][x+1]&1;
        if(y!=board.size()-1&&x!=board[0].size()-1)
            count += board[y+1][x+1]&1;
        return count;
    }
    
    void gameOfLife(vector<vector<int>>& board) {
        for(int i=0;i<board.size();i++)
        {
            for(int j=0;j<board[i].size();j++)
            {
                if(board[i][j]==1)
                {
                    if(getAliveNeighbors(board,j,i) < 2)
                    {
                        //nothing
                    }
                    else if(getAliveNeighbors(board,j,i) < 4)
                    {
                        board[i][j]*=3;
                    }
                }
                else if(getAliveNeighbors(board,j,i) == 3)
                    board[i][j]+=2;
            }
        }
        
        for(int i=0;i<board.size();i++)
        {
            for(int j=0;j<board[i].size();j++)
            {
                if(board[i][j]&2)
                {
                    board[i][j]=1;
                }
                else
                    board[i][j]=0;
            }
        }
    }
};

###### tags: `LeetCode` `C++`