这是有名的康威生命游戏, 描述的是一种细胞自动机。

对一个 M*N 的区域,每一个位置有两种状态,1为活细胞,0为死细胞,对于每个位置都满足如下的条件:

  1. 如果活细胞周围八个位置的活细胞数少于两个,则该位置活细胞死亡

  2. 如果活细胞周围八个位置有两个或三个活细胞,则该位置活细胞仍然存活

  3. 如果活细胞周围八个位置有超过三个活细胞,则该位置活细胞死亡

  4. 如果死细胞周围正好有三个活细胞,则该位置死细胞复活

我们用置换方法 in-place 来解题,不新建一个相同大小的数组,只更新原有数组。所有的位置在同一个周期必须被同时更新,但是在循环程序中我们还是一个位置一个位置更新的,那么当一个位置更新了,这个位置成为其他位置的 neighbor 时,我们怎么知道其未更新的状态呢,我们可以使用状态机转换:

状态0: 死细胞转为死细胞 (dead 黑色)

状态1: 活细胞转为活细胞 (old 红色)

状态2: 活细胞转为死细胞 (dead 黑色)

状态3: 死细胞转为活细胞 (young 粉色)

最后我们对所有状态对2取余,那么状态0和2就变成死细胞,状态1和3就是活细胞。

我们先对原数组进行逐个扫描,对于每一个位置,扫描其周围八个位置,前序细胞(左上/中上/右上/左)如果遇到状态1或2,就计数器累加1,后续细胞(右/右下/中下/左下)遇到取余为1,计数器也累加1。
扫完8个邻居,如果少于两个活细胞或者大于三个活细胞,而且当前位置是活细胞的话,标记状态2,如果正好有三个活细胞且当前是死细胞的话,标记状态3。

完成一遍扫描后对数据更新一遍,变成我们想要的结果。

GitHub repository

喜欢的话给一个 star 吧,

也可以互相 follow : )

Demo地址
img1