90. Game of Life

Given an m x n grid board of 0s (dead) and 1s (live), apply one step of Conway's Game of Life rules:
1. Live cell with 2 or 3 live neighbors → lives
2. Live cell with <2 or >3 live neighbors → dies
3. Dead cell with exactly 3 live neighbors → lives

Return the next state.

Input: A 2D binary array board of size m x n.

Output: The board after one step.

Examples

Input: [[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]]
Explanation: Apply rules to each cell simultaneously.

Input: [[1,1],[1,0]]
Output: [[1,1],[1,1]]
Explanation: Bottom-right dead cell has 3 live neighbors→lives.

Input: [[1]]
Output: [[0]]
Explanation: Single cell has 0 neighbors→dies.

Constraints

• m==board.length
• n==board[i].length
• 1<=m,n<=25
• board[i][j] is 0 or 1

Asked by