深色模式
289-生命游戏
题目参考：289. 生命游戏
题目描述
根据 百度百科 ， 生命游戏 ，简称为 生命 ，是英国数学家约翰·何顿·康威在 1970 年发明的细胞自动机。
给定一个包含 m × n 个格子的面板，每一个格子都可以看成是一个细胞。每个细胞都具有一个初始状态： 1 即为 活细胞 （live），或 0 即为 死细胞 （dead）。每个细胞与其八个相邻位置（水平，垂直，对角线）的细胞都遵循以下四条生存定律：
- 如果活细胞周围八个位置的活细胞数少于两个，则该位置活细胞死亡；
- 如果活细胞周围八个位置有两个或三个活细胞，则该位置活细胞仍然存活；
- 如果活细胞周围八个位置有超过三个活细胞，则该位置活细胞死亡；
- 如果死细胞周围正好有三个活细胞，则该位置死细胞复活；
下一个状态是通过将上述规则同时应用于当前状态下的每个细胞所形成的，其中细胞的出生和死亡是同时发生的。给你 m x n 网格面板 board 的当前状态，返回下一个状态。
示例 1：
py
输入：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：
py
输入：board = [[1,1],[1,0]]
输出：[[1,1],[1,1]]暴力破解
按照规则 ，访问矩阵每一个元素，然后按照规则修改。因为修改原矩阵，会影响后面位子计算结果，因此复制一个新的矩阵，存储计算结果，最后将计算结果复制给原矩阵。
复杂度分析
- 时间复杂度：
- 空间复杂度：
py
class Solution(object):
def gameOfLife(self, board):
"""
:type board: List[List[int]]
:rtype: None Do not return anything, modify board in-place instead.
"""
m = len(board)
n = len(board[0])
answer = [[0] * n for _ in range(m)]
for i in range(m):
for j in range(n):
count = 0
for x in range(max(0, i-1), min(i+1, m-1) +1):
for y in range(max(0, j-1), min(j+1, n -1) +1):
if x == i and y == j:
continue
if board[x][y] == 1:
count += 1
if board[i][j] == 1:
if count ==2 or count == 3:
answer[i][j] = 1
else:
answer[i][j] = 0
else:
if count == 3:
answer[i][j] = 1
else:
answer[i][j] = 0
for i in range(m):
for j in range(n):
board[i][j] = answer[i][j]原地修改
参考方案： 官方题解
主要思想：对于已经访问过的元素，计算后进行标记，类似日常中的涂色操作。
- 1-->0， 标记为 -1
- 0-->1, 标记为2
- 1-->1, 不做处理
- 0-->0, 不做处理
可以看到，当节点变化后，通过在原位置进行不同标记，然后进行恢复最终结果就行。
代码不再书写。