###### tags: `Leetcode` `medium` `array` `python` `c++`

# 289. Game of Life

## [題目連結:] https://leetcode.com/problems/game-of-life/

## 題目:
According to 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."

The board is made up of an ```m x n``` grid of cells, where each cell has an initial state: **live** (represented by a ```1```) or **dead** (represented by a ```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.

The next state is created by applying the above rules simultaneously to every cell in the current state, where births and deaths occur simultaneously. Given the current state of the ```m x n``` grid ```board```, return the next state.


## 解題想法:
* 題目為給一matrix，每個格子為一個細胞:
* **1**表示活
* **0**表示死
* 求下一個狀況，規則:
* 若該細胞目前**活**，則檢查其周圍(八格鄰居):
* 若鄰居有**2~3格為活**，則該細胞下個狀態為**活**
* 若鄰居**大於3格為活**，則該細胞下個狀態為**死**
* 若鄰居**小於2格為活**，則該細胞下個狀態為**死**
* 若該細胞目前**死**，則檢查其周圍(八格鄰居):
* 若鄰居**恰好有3格為活**，則該細胞下個狀態為**活**
* 直接更改input matrix，不要返回新的matrix

* **解題技巧**:
* **用二進制bit紀錄用以判斷該細胞**: 未來狀態與當前狀態
* 將新狀態紀錄到前面:
* ex: 當前細胞為0，該細胞下個狀態為1
* 則記錄該細胞為: **10**
* 最後將每格右移，即可in-place完成

* **流程**:
* Step1: 遍歷每個位置
* Step2: live=0，紀錄目前細胞的周圍鄰居為1的個數
* Step3: 判斷技巧
* 對於目前鄰居，需要與(01) 1做**and**
* 因為也許有些點原本是0結果下個狀態是1 因此已經被改成(10) 2了
* 但我們要以**當前狀態**評估，所以用與1做and
* Step4: 判斷此格的下個狀態，將下個狀態加到前面
* case1: 若該格目前為0
* 若恰三個鄰居為1，即live=3，表示該格下個狀態可活
* 則將該格改為2 (二進制10)
* case2: 若該格目前為1
* if 2<=live<=3: 下個狀態依舊為活
* 則將該格改為3 (二進制 11)
* else: 下個狀態為死
* 將該格改為1 (二進制01)
* 最終完成所有格後，將所有格右移更新為下個狀態

## Python:

class Solution(object):
    def gameOfLife(self, board):
        """
        :type board: List[List[int]]
        :rtype: None Do not return anything, modify board in-place instead.
        """
        m=len(board)
        n=len(board[0])
        #查看周圍8格
        check=[(-1,-1),(-1,0),(-1,1),(0,1),(0,-1),(1,1),(1,0),(1,-1)]
        #紀錄每隔的下一個狀態: 
        #將新的狀態記到前面 ex: 0下個狀態為1 則=> 10 = 新值為2
        for i in range(m):
            for j in range(n):
                #鄰居為1的個數
                live=0
                for neiberX,neiberY in check:
                    x=i+neiberX
                    y=j+neiberY
                    #若出界則不進行動作
                    if x<0 or x>=m or y<0 or y>=n:
                        continue
                    #判斷技巧!!! 要與01做and 才不會錯誤
                    #因為也許有些點原本是0結果下個狀態是1 因此已經被改成(10) 2了
                    #但我們還是要以當前狀態評估 所以用與1做and
                    if (board[x][y]&1)==1:
                        live+=1
                #判斷此格的下個狀態 將下個狀態加到前面
                if board[i][j]==0:
                    if live==3: #三個鄰居為1 下個狀態可活
                        board[i][j]=2  #為二進制 10
                else: #原本是1了
                    if 2<=live<=3: #下個狀態依舊為活
                        board[i][j]=3  #為二進制 11
                    else:
                        board[i][j]=1  #為二進制 01
        #更新為下個狀態 全部值右移
        for i in range(m):
            for j in range(n):
                board[i][j]>>=1
                        
result=Solution()
board = [[0,1,0],[0,0,1],[1,1,1],[0,0,0]]
print("Original:",board)
result.gameOfLife(board)
print("After: ",board)

## C++:

class Solution {
public:
    void gameOfLife(vector<vector<int>>& board) {
        int m=board.size(), n=board[0].size(), live=0;
        vector<vector<int>> dirs={{1,0}, {-1,0}, {0,1}, {0,-1}, {1,1}, {-1,-1}, {-1,1}, {1,-1}};
        for (int i=0; i<m; i++){
            for (int j=0; j<n; j++){
                live=0;
                //check neighbor
                for (auto &nums: dirs){
                    int tmpx=i+nums[0], tmpy=j+nums[1];
                    if (tmpx>=0 && tmpx<m && tmpy>=0 && tmpy<n){
                        if ((board[tmpx][tmpy]&1)==1)
                            live+=1;
                    }
                }
                //Update the next state of the current cell
                if (board[i][j]==0){
                    if (live==3)
                        board[i][j]=2; //(10)
                }
                else{
                    if (2<=live && live<=3) //life
                        board[i][j]=3; //(11)
                    else //die
                        board[i][j]=1; //(01)
                }   
            }
        }
        for (int i=0; i<m; i++){
            for (int j=0; j<n; j++){
                board[i][j]>>=1;
            }
        } 
    }
};