1. Description of the problem
The game of Life
English description
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.
Example 1:
Input: board = [[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]]Example 2:
Input: board = [[1, 1], [1, 0]]
Output: [[1, 1], [1, 1]]Constraints:
m == board.length
n == board[i].length
1 <= m, n <= 25
board[i][j] is 0 or 1.
Follow up:
- Could you solve it in-place? Remember that the board needs to be updated simultaneously: You cannot update some cells first and then use their updated values to update other cells.
- In this question, we represent the board using a 2D array. In principle, the board is infinite, which would cause problems when the active area encroaches upon the border of the array (i.e., live cells reach the border). How would you address these problems?
Product description
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,1,0],[0,0,1],[1,1],[0,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:
m == board.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?
Source: LeetCode link: leetcode-cn.com/problems/ga… Copyright belongs to the Collar buckle network. Commercial reprint please contact official authorization, non-commercial reprint please indicate the source.
Second, the idea of solving the problem
[Game of Life]
Add new states 2 (alive now, dead after update), -1 (dead now, alive after update). In this way, the status can be directly updated after traversing the surrounding cells of the grid;
- Board [I][J] == 1 was changed to board[I][J] >= 1;
- After traversing the array, iterate again to update the cells in the state -1 and 2 to 1 and 0 respectively.
Three, AC code
C++
class Solution { public: void gameOfLife(vector<vector<int>>& board) { for(int i = 0; i < board.size(); i++) { for(int j = 0; j < board[0].size(); j++) { int numOfLive = getNumOfLive(i, j, board); If (board [I] [j]) {/ / define a new condition 2: the current for live cells, but the updated for the dead cells if (numOfLive < 2 | | numOfLive > 3) board [I] [j] = 2; If (numOfLive == 3) board[I][j] = -1; if(numOfLive == 3) board[I][j] = -1; For (int I = 0; i < board.size(); i++) { for(int j = 0; j < board[0].size(); j++) { if(board[i][j] > 1) board[i][j] = 0; else if(board[i][j] < 0) board[i][j] = 1; Int getNumOfLive(int x, int y, vector<vector<int>> &board) {int num = 0, row = board.size(), col = board[0].size(); for(int i = -1; i < 2; i++) { int posX = x + i; for(int j = -1; j < 2; j++) { int posY = y + j; If (I == 0 &&j == 0) continue; / / beyond the boundary position not to count the if (posX < 0 | | posX > = row | | posY < 0 | | posY > = col) continue; If (board[posX][posY] >= 1) num++; if(board[posX][posY] >= 1) num++; } } return num; }};Copy the codeJava
class Solution { public void gameOfLife(int[][] board) { for(int i = 0; i < board.length; i++) { for(int j = 0; j < board[0].length; j++) { int numOfLive = getNumOfLive(i, j, board); If (board [I] [j] = = 1) {/ / define a new condition 2: the current for live cells, but the updated for the dead cells if (numOfLive < 2 | | numOfLive > 3) board [I] [j] = 2; If (numOfLive == 3) board[I][j] = -1; if(numOfLive == 3) board[I][j] = -1; For (int I = 0; i < board.length; i++) { for(int j = 0; j < board[0].length; j++) { if(board[i][j] > 1) board[i][j] = 0; else if(board[i][j] < 0) board[i][j] = 1; } } } public int getNumOfLive(int x, int y, int[][] board) { int num = 0, row = board.length, col = board[0].length; for(int i = -1; i < 2; i++) { int posX = x + i; for(int j = -1; j < 2; j++) { int posY = y + j; If (I == 0 &&j == 0) continue; / / beyond the boundary position not to count the if (posX < 0 | | posX > = row | | posY < 0 | | posY > = col) continue; If (board[posX][posY] >= 1) num++; if(board[posX][posY] >= 1) num++; } } return num; }}Copy the codeFourth, the problem solving process
The first stroke
Seeing in situ algorithm, two techniques come to mind — dynamic programming and sliding Windows. [Considering the complexity of implementation and optimization space, it is proved not feasible]
One is dynamic programming. Suppose there is a partial overlap between the number of living cells near the current cell and the next cell according to the method from left to right
So is it possible to update on this basis, for example, to find the number of living cells in the yellow square? Currently, we know the number of living cells in the purple square, so we only need to record the number of living cells in the green square and traverse the blue square
This reduced the number of traversals from eight to three, which did reduce the amount of rework. But there are a lot of boundary issues that need to be considered, like setting initial conditions, right? Go through in S order, okay? Increased programming complexity, not a good choice.
The second is the sliding window (refers to a certain order through all the cells).
Thinking of putting two more layers on top
When traversing the current cell, place the result of the next update to that location on the center square of the previous layer
When the update is complete, shift the data from the previous two rows down.
However, this requires an additional O(N) space (assuming the size is M * N), and finally requires a total translation of the data, which is really unaffordable read and write overhead.
The second stroke
The official idea is to add states. For example, there were originally only two states, 0 (death) and 1 (survival).
Now add two states 2 (alive now, dead after update) and -1 (dead now, alive after update).
In this way, you can safely modify the data in place:
- Board [I][J] == 1 was changed to board[I][J] >= 1;
- After traversing the array, iterate again to update the cells in the state -1 and 2 to 1 and 0 respectively.
Guys, put 666 on the screen!
It was rewritten in Java
