[289][中等] 生命游戏

题目描述

289. 生命游戏

根据 百度百科 ，生命游戏，简称为生命，是英国数学家约翰·何顿·康威在 1970 年发明的细胞自动机。

给定一个包含 m × n 个格子的面板，每一个格子都可以看成是一个细胞。每个细胞都具有一个初始状态：1 即为活细胞（live），或 0 即为死细胞（dead）。每个细胞与其八个相邻位置（水平，垂直，对角线）的细胞都遵循以下四条生存定律：

• 如果活细胞周围八个位置的活细胞数少于两个，则该位置活细胞死亡；

• 如果活细胞周围八个位置有两个或三个活细胞，则该位置活细胞仍然存活；

• 如果活细胞周围八个位置有超过三个活细胞，则该位置活细胞死亡；

• 如果死细胞周围正好有三个活细胞，则该位置死细胞复活；

下一个状态是通过将上述规则同时应用于当前状态下的每个细胞所形成的，其中细胞的出生和死亡是同时发生的。给你 m x n 网格面板 board 的当前状态，返回下一个状态。

示例 1：

输入：board = [[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：

输入：board = [[1,1],[1,0]]
输出：[[1,1],[1,1]]

提示：

• m == board.length

• n == board[i].length

• 1 <= m, n <= 25

• board[i][j] 为 0 或 1

进阶：

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

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

解题思路

如果你直接根据规则更新原始数组, 那么就做不到题目中说的同步更新. 假设你直接将更新后的细胞状态填入原始数组, 那么当前轮次其他细胞状态的更新就会引用到当前轮已更新细胞的状态, 但实际上每一轮更新需要依赖上一轮细胞的状态, 是不能用这一轮的细胞状态来更新的.

不使用原地算法

如果将原来的矩阵直接拷贝一份, 然后再更新, 就不会有上面的问题了.

一个巧妙的方法是使用卷积核. 根据题目可以看到对于每个位置状态变化的关键是计算它相邻的8个位置值为1的数量. 因此可以使用如下的卷积核计算:

[1, 1, 1]
[1, 0, 1]
[1, 1, 1]

而由于只关心1的数量, 可以对周围使用0进行padding. 然后使用numpy计算卷积的方法快捷操作, 具体方法参考: 【🐼熊猫刷题Python3】包学包会，CV中的卷积.

使用原地算法

对于这种有限状态变化, 且原地操作的题目, 关键核心在于在原位置上修改, 且定义更多的复合状态, 新状态同时包含之前的状态和新状态.

根据题目的4个规律, 可以总结如下:

可以总结为:

• 原来为0, 现在还是0

• 原来是1, 现在还是1

• 原来是0, 现在是1

• 原来是1, 现在是0

前两种情况状态没有变化, 不会影响周围位置的计数. 但后两种情况状态发生了改变, 如果直接赋值1或0, 就会影响之后相邻位置的统计. 因此对于后两种情况, 设定两种新状态, 两种复合状态:

• 2: 代表原来是0, 现在是1

• 3: 原来是1, 现在是0

因此现在见到了0, 1, 2, 3, 就可以知道原来的状态是什么, 而且也存储了新状态.

根据这个思路, 就可以先遍历一遍数组更新状态, 然后再遍历一遍将2, 3装换为0, 1.

改进

上面的方法有两个小问题:

• 对于每个位置, 都要遍历一遍周围的位置, 这样相当于每个位置平均被周围的访问8遍

• 新定义的状态2, 3比较抽象, 不宜懂

那么在定义状态的时候, 可以直接使用双位数AB, A表示周围1的数量, B表示之前的状态. 这样我们在第一次遍历时, 就可以只关心数组中的1, 然后去影响周围的位置, 给他们的A位加上1. 然后在第二次遍历时, 根据每一位的之前状态和周围1的数量, 就可以更新了.

代码如下:

class Solution:
    def gameOfLife(self, board: List[List[int]]) -> None:
        """
        Do not return anything, modify board in-place instead.
        """
        n, m = len(board), len(board[0])
        direction = list(itertools.permutations([-1, 0, 1], 2)) + [(-1, -1), (1, 1)]

        for i in range(n):
            for j in range(m):
                if board[i][j] % 10 == 1:
                    for di, dj in direction:
                        ii, jj = i + di, j + dj
                        if 0 <= ii < n and 0 <= jj < m:
                            board[ii][jj] += 10

        for i in range(n):
            for j in range(m):
                raw, count = board[i][j] % 10, board[i][j] // 10
                if raw == 0 and count == 3:
                    board[i][j] = 1
                elif raw == 1:
                    if count > 3:
                        board[i][j] = 0
                    elif count < 2:
                        board[i][j] = 0
                    else:
                        board[i][j] = 1
                else:
                    board[i][j] = 0