289.-game-of-life.md

289. Game of Life

• Medium

• 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):

  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.

  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.

Analysis

This problem is not different from other questions of the same type, the only thing is that it has more rules. What we want to do is to go through all the cells and see what they will become and change it using another indicator other than 0 and 1. Here in the solution, 0 and 2 both means dead and 1 and 3 means live.

Then after we have went through all the cells, we change all the 2s to 0 and all the 3s to 1.

class Solution:
    def gameOfLife(self, board):
        m,n = len(board), len(board[0])
        for i in range(m):
            for j in range(n):
                if board[i][j] == 0 or board[i][j] == 2:
                    if self.nnb(board,i,j) == 3:
                        board[i][j] = 2
                else:
                    if self.nnb(board,i,j) < 2 or self.nnb(board,i,j) >3:
                        board[i][j] = 3
        for i in range(m):
            for j in range(n):
                if board[i][j] == 2: board[i][j] = 1
                if board[i][j] == 3: board[i][j] = 0
                    
                    
    
    def nnb(self, board, i, j):
        neighbors = [(0, 1), (0, -1), (1, 0), (-1, 0), (-1, -1), (1, 1), (-1, 1), (1, -1)]
        count = 0
        m, n = len(board), len(board[0])
        for d in neighbors:
            if 0 <= i + d[0] < m and 0 <= j + d[1] < n:
                count += board[i + d[0]][j + d[1]] % 2 
        return count