289.生命游戏题目来源：https://leetcode-cn.com/problems/game-of-life/题目根据百度百科，生命游戏，简称生命，是英国数学家约翰·霍顿发明的元胞自动机Conway于1970年提出。给定一个由m×n网格组成的面板，每个网格都可以视为一个单元格。每个细胞都有一个初始状态：活细胞为1，死细胞为0。每个细胞及其相邻八个位置（水平、垂直、对角）的细胞遵循以下四个生存规律：如果活细胞周围八个位置的活细胞数量少于两个，则该位置的活细胞将死;如果活细胞周围八个位置有两个或三个活细胞，则该位置的活细胞还活着；如果活细胞周围八个位置有三个以上的活细胞，则该位置的活细胞已死亡；如果有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]]进阶：你能用原地算法解决这道题吗？注意，面板上的所有网格需要同时更新：不能先更新一些网格，然后再用它们更新的值来更新其他网格。在这道题中，我们用一个二维数组来表示面板。原则上，面板是无限的，但是当活细胞侵占面板边界时，这会导致问题。你将如何解决这些问题？解题思路：使用额外的状态标记来模拟问题，需要原位算法来求解问题。考虑先使用一个额外的状态来标记，当面板中所有格子的状态整理完毕后，再根据状态修正细胞存活状态。先明确一下题目的四大生存法则：生存法则1：如果活细胞周围八个位置的活细胞数量少于两个，则该位置的活细胞就会死亡。如下图所示：生存法则二：如果活细胞周围八个位置有两个或三个活细胞，则该位置的活细胞还活着，见下图：生存法则三：如果有更多活细胞周围八个位置超过三个活细胞如果有活细胞，则该位置的活细胞将死亡，如下图：生存法则4：如果死细胞周围恰好有三个活细胞，这个位置的死细胞会复活，如下图：以上就是题目中提到的四大生存法则。现在整理一下，使用附加状态来标记单元格的状态。这是因为在标题中提到了，【所有网格需要同时更新：不能更新一些网格，然后用更新后的值去更新其他网格】。所以现在考虑，是否使用附加状态进行标记。如果细胞之前的状态是活的，那么当它满足法则1或3时，就会变成死状态。此时，它会被标记为‘垂死’。这里需要注意的是，在标记为‘dying’时，要记住cell的原始状态是活的状态，当它作为其他cell的相邻cell时，应该视为a活状态（即值为1）进行计算。例如：如果细胞之前是死的，那么当它符合生存第四定律时就会复活。此时，将其标记为relive。这里需要注意的是和上面的情况类似。当细胞与其他细胞相邻时，应将其视为死亡状态。具体算法：遍历原面板中的单元格；根据四个生存法则计算出当前cell的新状态，必要时进行标记。注意flag的状态，当'dying'是相邻cell时，应该是living状态，反之，'relive'作为相邻cell时，应该是dead状态。根据标记的状态重新遍历更新。将标记为'dying'的单元格的值更改为0，将标记为relive的单元格的值更改为1。具体实现如下。代码实现#-*-coding:utf-8-*-"""@Time:2020/4/29:52@File:game_of_life.py@Author:Demon@Contact:yiluolion@126.com"""#将导入库从这里输入importListclass解决方案：defgameOfLife(self,board:List[List[int]])->None:"""不要返回任何东西，而是就地修改board。"""#大约八相邻位置方向=[(-1,0),(-1,-1),(0,-1),(1,-1),(1,0),(1,1),(0,1),(-1,1)]rows=len(board)cols=len(board[0])forrowinrange(rows):forcolinrange(cols):#用来标记存活细胞的数量=0#查看dx,dy在方向上的相邻位置：r=row+dxc=col+dyif(r>=0andr
