A cellular automaton runs on an m x n grid cells of 0 (dead) and 1 (alive) whose edges wrap around: the cell to the right of the last column is the first column of the same row, and the cell below the last row is the first row of the same column. Every cell has exactly eight neighbours.
Compute one generation using these rules and return the new grid (do not modify the input):
- a live cell with 2 or 3 live neighbours stays alive, otherwise it dies;
- a dead cell with exactly 3 live neighbours becomes alive.
Examples
Input: cells = [[0, 0, 0, 0], [0, 1, 1, 1], [0, 0, 0, 0], [0, 0, 0, 0]]
Output: [[0, 0, 1, 0], [0, 0, 1, 0], [0, 0, 1, 0], [0, 0, 0, 0]]
Explanation: the horizontal bar of three becomes a vertical bar.
Input: cells = [[0, 0, 0], [1, 1, 1], [0, 0, 0]]
Output: [[1, 1, 1], [1, 1, 1], [1, 1, 1]]
Explanation: with wrapping, every cell in rows 0 and 2 sees all three live cells,
and each end of the bar sees the other end as a neighbour.
Constraints
3 <= m, n <= 200- Target: O(m * n) time.
Goals
- Count the eight neighbours of every cell with wrap-around at the edges
- Compute a new grid from the old one without corrupting the input mid-step
- Apply birth and survival rules exactly