This is the famous Conway Game of Life, which describes a cellular automaton.
For an M*N region, each position has two states, 1 for live cells and 0 for dead cells, and the following conditions are met for each position:
-
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 at eight locations around a living cell, the living cell at that location dies
-
If there are exactly three living cells around the dead cell, the dead cell revives at that location
Instead of creating a new array of the same size, just update the existing array. All positions must be updated at the same time in the same cycle, but in the loop program, we still update position by position, so when a position is updated, this position becomes a neighbor of other positions, how do we know its unupdated state? We can use the state machine conversion:
State 0: Dead cells turn dead (black)
State 1: Living cells become living cells (old red)
State 2: Living cells turn dead (black)
State 3: Dead cells turn into live cells (Young pink)
And then finally we mod all the states with respect to 2, so states 0 and 2 are dead, and states 1 and 3 are alive.
First, we scan the original array one by one. For each position, we scan the eight surrounding positions. If the preceding cell (upper left/upper middle/upper right/left) encounters state 1 or 2, the counter is accumulated by 1, and the subsequent cell (right/lower right/lower middle/lower left) encounters state 1, so is the counter. After scanning all 8 neighbors, mark state 2 if there are less than two live cells or more than three live cells and the current location is live cells, mark state 3 if there are exactly three live cells and the current location is dead cells.
After completing a scan, update the data to get the result we want.
The Demo address
