问题描述

根据“生命游戏”规则，给定一个m x n的二维网格，每个格子代表一个细胞，每个细胞有两种状态：

• 1 表示活细胞
• 0 表示死细胞

细胞与周围的8个细胞（水平、垂直、对角线）都存在联系，每个细胞的状态根据以下规则变化：

1. 活细胞如果周围的活细胞数少于2个，则死亡；
2. 活细胞如果周围的活细胞数为2或3个，则继续存活；
3. 活细胞如果周围的活细胞数多于3个，则死亡；
4. 死细胞如果周围的活细胞数正好是3个，则变成活细胞。

所有细胞的状态变化是同时发生的。

格式

输入

• 一个m行n列的二维整数网格，每个位置为0或1。

输出

• 一个m行n列的二维整数网格，表示更新后的状态。

样例

样例1

输入

4 3
0 1 0
0 0 1
1 1 1
0 0 0

输出

0 0 0
1 0 1
0 1 1
0 1 0

样例2

输入

2 2
1 1
1 0

输出

1 1
1 1

提示

• 1 <= m, n <= 25
• 每个格子的初始状态为 0 或 1

进阶

• 你是否可以使用原地算法完成这道题？请注意同时更新所有格子的状态，不能先更新部分格子再用它们的结果去更新其他格子。
• 题目中使用的二维数组有边界限制，但在“生命游戏”的完整规则中，细胞数量是无限的。你能考虑如何扩展这个规则吗？