Topic describes

The Game of Life, or Life for short, is a cellular automaton invented by British mathematician John Holden Conway in 1970, according to Baidu Encyclopedia.

Given a panel of m by N cells, each cell can be thought of as a cell. Each cell has an initial state: 1 is live, or 0 is dead. Each cell and its eight adjacent cells (horizontal, vertical, and diagonal) follow the following four rules of survival:

  • If there are less than two living cells at eight sites around a living cell, the living cells at that site die;
  • If there are two or three living cells in eight locations around a living cell, that location is still alive;
  • If there are more than three living cells in eight locations around a living cell, the living cells in that location die;
  • If there are three living cells around the dead cell, the dead cell revives at that location;

The next state is formed by applying the above rules simultaneously to each cell in the current state, where cell birth and death occur simultaneously. Give you the current state of the m x N grid panel board, return to the next state.

Example 1:

Input: board = [[0, 0], [0, 1],,1,1 [1], [0, 0]] output: [[0, 0], [1, 1], [0,1,1], [0, 0]]

Example 2:

Input: board = [1,1],[1,0]] output: [[1,1],[1,1]]

Tip:

Length n == board[I]. Length 1 <= m, n <= 25 Board [I][j] is 0 or 1

Advanced:

Can you use the in situ algorithm to solve this problem? Note that all cells on the panel need to be updated at the same time: you cannot update some cells and then use their updated values to update others. In this case, we use a two-dimensional array to represent the panel. In principle, panels are infinite, but this can cause problems when living cells encroach on panel boundaries. How would you solve these problems?

Copyright belongs to LeetCode. Commercial reprint please contact official authorization, non-commercial reprint please indicate the source.

Thought analysis

By copying a matrix, loop through the conditions, pay attention to the boundary problems, and finally write the data back to the original matrix

AC code

void gameOfLife(int** board, int boardSize, int* boardColSize){
    int cache[boardSize][boardColSize[0]].for (int i = 0; i < boardSize; ++i) {
        for (int j = 0; j < boardColSize[i]; ++j) { cache[i][j] = board[i][j]; }}for (int i = 0; i < boardSize; ++i) {
        for (int j = 0; j < boardColSize[i]; ++j) {
            int live = 0;

            int l = i - 1> =0;
            int r = i + 1 < boardSize;
            int t = j - 1> =0;
            int b = j + 1 < boardColSize[i];
            int lt = l && t;
            int lb = l && b;
            int rt = r && t;
            int rb = r && b;

            if (l && board[i - 1][j]) {
                live++;
            }
            if (r && board[i + 1][j]) {
                live++;
            }
            if (t && board[i][j - 1]) {
                live++;
            }
            if (b && board[i][j + 1]) {
                live++;
            }
            if (lt && board[i - 1][j - 1]) {
                live++;
            }
            if (lb && board[i - 1][j + 1]) {
                live++;
            }
            if (rt && board[i + 1][j - 1]) {
                live++;
            }
            if (rb && board[i + 1][j + 1]) {
                live++;
            }

            if (live < 2 || live > 3) {
                cache[i][j] = 0;
            }
            if (live == 3) {
                cache[i][j] = 1; }}}for (int i = 0; i < boardSize; ++i) {
        for (int j = 0; j < boardColSize[i]; ++j) { board[i][j] = cache[i][j]; }}}Copy the code

conclusion

A conditional logic problem, pay attention to dealing with boundary problems

This article is participating in the “Nuggets 2021 Spring Recruitment Campaign”, click to see the details of the campaign