【LeetCode】生命游戏


一、题目

根据 百度百科 , 生命游戏 ,简称为 生命 ,是英国数学家约翰·何顿·康威在 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

进阶:

你可以使用原地算法解决本题吗?请注意,面板上所有格子需要同时被更新:你不能先更新某些格子,然后使用它们的更新后的值再更新其他格子。
本题中,我们使用二维数组来表示面板。原则上,面板是无限的,但当活细胞侵占了面板边界时会造成问题。你将如何解决这些问题?


二、解法

根据四条生存定律,可以发现
if 活细胞:
if 2、3活细胞:存活
else: 死亡
if 死细胞:
if 周围3活细胞:复活
else:死亡
因为答案要的是下一个面板上,细胞的存活状态。
我们模拟就好了,而且可以不利用额外空间,我们在原地记录。
定义以下规则:

当前状态 下一个状态 标识
活1 活1 3
活1 死0 2
死0 死0 -1
死0 活1 -2

完整代码

class Solution:
    def gameOfLife(self, board: List[List[int]]) -> None:
        dir = [[-1,-1],[0,-1],[1,-1],[-1,0],[1,0],[-1,1],[0,1],[1,1]]
        m, n = len(board), len(board[0])
        for i in range(m):
            for j in range(n):
                alive = 0
                for di, dj in dir:
                    ci, cj = i + di, j + dj
                    if 0 <= ci < m and 0 <= cj < n and board[ci][cj] in (1, 2, 3):
                    	# 是活的,1:还没遍历到的活的,2和3:遍历过了,原本是活的
                        alive += 1
                if board[i][j]:
                	# 两个或者三个,活
                    if alive in (2, 3):
                        board[i][j] = 3
                    else:
                        board[i][j] = 2
                else:
                	# 刚好三个,复活
                    if alive == 3:
                        board[i][j] = -2
                    else:
                        board[i][j] = -1
        for i in range(m):
            for j in range(n):
                if board[i][j] in (3, -2):
                    board[i][j] = 1
                else:
                    board[i][j] = 0

相关推荐

  1. Python康威生命游戏

    2024-07-10 22:54:04       39 阅读
  2. 康威生命游戏

    2024-07-10 22:54:04       25 阅读

最近更新

  1. docker php8.1+nginx base 镜像 dockerfile 配置

    2024-07-10 22:54:04       4 阅读
  2. Could not load dynamic library ‘cudart64_100.dll‘

    2024-07-10 22:54:04       5 阅读
  3. 在Django里面运行非项目文件

    2024-07-10 22:54:04       4 阅读
  4. Python语言-面向对象

    2024-07-10 22:54:04       4 阅读

热门阅读

  1. 奇幻的Python

    2024-07-10 22:54:04       9 阅读
  2. 记录一些简单的linux运维命令

    2024-07-10 22:54:04       8 阅读
  3. python--del

    2024-07-10 22:54:04       8 阅读
  4. BiLSTM模型实现

    2024-07-10 22:54:04       10 阅读
  5. Vue2.0和Vue3.0的区别?

    2024-07-10 22:54:04       11 阅读
  6. 网络安全应急处理流程

    2024-07-10 22:54:04       10 阅读
  7. 算法·高精度

    2024-07-10 22:54:04       7 阅读
  8. 闲聊C++与面向对象思想

    2024-07-10 22:54:04       8 阅读
  9. 路由器中 RIB 与 FIB 的区别

    2024-07-10 22:54:04       13 阅读
  10. 生成日志系统和监控

    2024-07-10 22:54:04       11 阅读
  11. Apache Spark详解

    2024-07-10 22:54:04       8 阅读
  12. qt opencv 应用举例

    2024-07-10 22:54:04       8 阅读