4.4　生命游戏

题目描述（第289题）

生命游戏是英国数学家约翰·何顿·康威在1970年发明的细胞自动机。

给定一个包含mn个格子的面板，每个格子都可以被看成一个细胞。每个细胞具有一个初始状态：live(1)，即活细胞；或dead(0)，即死细胞。每个细胞与其8个相邻位置（水平、垂直、对角线）的细胞都遵循以下4条生存定律。

1.如果活细胞周围8个位置的活细胞数少于2个，则该位置活细胞死亡。

2.如果活细胞周围8个位置有2个或3个活细胞，则该位置活细胞仍然存活。

3.如果活细胞周围8个位置有超过3个活细胞，则该位置活细胞死亡。

4.如果死细胞周围正好有3个活细胞，则该位置死细胞复活。

根据当前状态，写一个函数来计算面板上细胞的下一个（一次更新后的）状态。下一个状态是通过将上述规则同时应用于当前状态下的每个细胞所形成的，其中细胞的出生和死亡是同时发生的。

示例

输入：

输出：

进阶

你可以使用原地算法解决本题吗？请注意，面板上所有格子需要同时被更新：你不能先更新某些格子，然后使用它们的更新后的值再更新其他格子。

本题中，我们使用二维数组来表示面板。原则上，面板是无限的，但当活细胞侵占了面板边界时会造成问题。你将如何解决这些问题？

背景

生命游戏乍看起来平淡无奇，游戏过程无人干预，细胞初始状态和4条生存定律决定了之后的一切。然而恰恰在这样简单的设定之下，看似杂乱无序的细胞不断诞生和消亡，逐渐演化出各种精致的结构形态；随着时间的推移，有的结构会变得十分稳定，有的则规律地震荡，还有的甚至会在空间中移动并与其他结构发生交互，俨然构成一副生命的图景。

因为这些特点，生命游戏广受计算机科学研究者的喜爱，大家争相构建自己的生命系统，甚至有人用它构建图灵机，大名鼎鼎的Emacs编辑器在很早的时期就内置了这个游戏。了解这些背景后你是否对本题兴趣大增呢？让我们看一看如何自己实现“生命”的演进吧。

思路

题目对具体场景和生存条件的描述非常清楚，因此实现思路也有章可循，根据题目分析实现的重点。

●　计算细胞邻居个数，即8个相邻位置存在的细胞数。

●　根据计算结果决定每个细胞的生死状态，即0或1。

先来看一下细胞邻居个数的计算。根据数组下标连续的特点，使用当前细胞的坐标值计算出邻居细胞的位置获取状态，如当前细胞为board[i][j]，则其上边的邻居为board[i-1][j]，右边的邻居为board[i][j+1]；因为空间有限的设定，计算时需要注意边界条件，当细胞处在空间边缘、顶点位置时潜在邻居的数目会小于8个。定义top、bottom、left、right 等4个变量对取值范围进行预处理，当邻居的坐标超出给定数组范围时移动边界。如下面的代码所示。

得到邻居细胞数量之后，我们要借助它判定并更新细胞的状态。根据设定，在每轮游戏中，所有细胞要同时更新状态，因此无法在一次遍历中完成判定与更改，我们将这个过程分为两个步骤。

●　遍历所有细胞计算邻居细胞的数量，根据生存法则判定并记录下一回合对应的状态。

●　状态判定完成后，重新遍历所有细胞依照记录更新状态。

基于上述分析，我们已经能够进行基本的实现了，题目还有进阶的条件限定，要求我们使用原地算法，这意味着在第一步不能使用额外的数组存放下一回合状态的记录。为避免在标记过程中使用1和0两个状态影响后续细胞的遍历，约定使用-1表示当前回合为1且下一回合应变为0的状态，使用-2表示当前回合为0且下一回合应变为1的状态；相应地，在进行邻居细胞计算时，遇到-1也认为当前该位细胞为存活状态，虽然下一回就会死亡。

完成所有状态的判定后，再进行一次遍历，将-1和-2设置为0和1，这道题目就完美解决了。下面是基于上面思路实现的Python代码。

代码

复杂度分析

●　时间复杂度：由循环遍历的方法可以得出时间复杂度为O(mn)，m和n分别为board数组的行数、列数。

●　空间复杂度：采用原地算法，空间复杂度为O(1)。