Game of Life
Medium · matrix
A grid is made of cells, each either alive (1) or dead (0). The neighbours of a cell are the up to eight cells that touch it, including the diagonal ones. Positions beyond the edge of the grid count as dead.
The grid moves forward one step. Every cell changes at the same moment, using the neighbour counts of the grid as it was *before* the step:
- A live cell with two or three live neighbours stays alive. With fewer than two or more than three, it dies.
- A dead cell with exactly three live neighbours comes alive.
- Every other cell stays dead.
Return the grid after one step.
Examples
Example 1
Input: board = [[0, 1, 0], [0, 1, 0], [0, 1, 0]]
Output: [[0, 0, 0], [1, 1, 1], [0, 0, 0]]
The middle cell of the column has two live neighbours and lives. The two cells beside it each have three live neighbours and come alive. The top and bottom cells each have one live neighbour and die.
Example 2
Input: board = [[1, 1], [1, 1]]
Output: [[1, 1], [1, 1]]
Every cell has exactly three live neighbours, so all of them stay alive.
Example 3
Input: board = [[1, 0], [0, 0]]
Output: [[0, 0], [0, 0]]
The only live cell has no live neighbours and dies. No dead cell has three.
Constraints
- 1 <= number of rows <= 50
- 1 <= number of columns <= 50
- Every cell is 0 or 1.