# Leetcode 289. Game of Life

## 題解

### Use Extra Memoery to evulate the cell

from copy import deepcopy

class Solution:
    def gameOfLife(self, board: List[List[int]]) -> None:
        """
        Do not return anything, modify board in-place instead.
        """
        # Time complexity: O(m*n)
        # Space complexity: O(m*n)
        m,n = len(board),len(board[0])
        temp = deepcopy(board)
        directions = [[0,-1],[1,0],[-1,0],[0,1],[-1,-1],[1,-1],[-1,1],[1,1]]
        for y in range(m):
            for x in range(n):
                cells = 0
                for _x,_y in directions:
                    new_x = x + _x
                    new_y = y + _y
                    if 0 <= new_x < n and 0 <= new_y < m:
                        cell = temp[new_y][new_x]
                        if cell == 1:
                            cells += 1
                if cells == 3:
                    board[y][x] = 1
                elif cells < 2 or cells > 3:
                    board[y][x] = 0

        # 3 -> 1
        # 2 -> no action
        # < 2 -> 0
        # > 3 -> 0

### Space Complexity O(1)

<iframe width="100%" height="500" src="https://www.youtube.com/embed/fei4bJQdBUQ?si=s6lqe9L6JnUuqKct" title="YouTube video player" frameborder="0" allow="accelerometer; autoplay; clipboard-write; encrypted-media; gyroscope; picture-in-picture; web-share" allowfullscreen></iframe>

from copy import deepcopy

class Solution:
    def gameOfLife(self, board: List[List[int]]) -> None:
        """
        Do not return anything, modify board in-place instead.
        """
        # Time complexity: O(m*n)
        # Space complexity: O(1)
        m,n = len(board),len(board[0])
        directions = [[0,-1],[1,0],[-1,0],[0,1],[-1,-1],[1,-1],[-1,1],[1,1]]
        for y in range(m):
            for x in range(n):
                cells = 0
                for _x,_y in directions:
                    new_x = x + _x
                    new_y = y + _y
                    if 0 <= new_x < n and 0 <= new_y < m:
                        cell = board[new_y][new_x]
                        if cell in [1,3]: # 只有 1 需要被視為活著的細胞
                            cells += 1
                if board[y][x]: # 如果為 1
                    if cells in [2,3]: # 保持狀態
                        board[y][x] = 3
                elif cells == 3: # 如果為 0 並且細胞需要再生
                    board[y][x] = 2
                # 其他狀態不需要管 1 -> 0 先視為 1 ，以便計算活著的細胞，0 -> 0 也不需要管
        # 轉換狀態
        for y in range(m):
            for x in range(n):
                if board[y][x] == 1:
                    board[y][x] = 0
                elif board[y][x] in [2,3]:
                    board[y][x] = 1

        # 3 -> 1
        # 2 -> no action
        # < 2 -> 0
        # > 3 -> 0
           
        # origin transfrom -> replace
        # 0 0 -> 0
        # 1 0 -> 1 # 0b10 => 2
        # 0 1 -> 2 # 0b01 => 1
        # 1 1 -> 3