LeetCode289、生命游戏

题目描述

根据 百度百科 ， 生命游戏 ，简称为 生命 ，是英国数学家约翰·何顿·康威在 1970 年发明的细胞自动机。 给定一个包含 m × n 个格子的面板，每一个格子都可以看成是一个细胞。每个细胞都具有一个初始状态： 1 即为 活细胞 （live），或 0 即为 死细胞 （dead）。每个细胞与其八个相邻位置（水平，垂直，对角线）的细胞都遵循以下四条生存定律： 如果活细胞周围八个位置的活细胞数少于两个，则该位置活细胞死亡； 如果活细胞周围八个位置有两个或三个活细胞，则该位置活细胞仍然存活； 如果活细胞周围八个位置有超过三个活细胞，则该位置活细胞死亡； 如果死细胞周围正好有三个活细胞，则该位置死细胞复活； 下一个状态是通过将上述规则同时应用于当前状态下的每个细胞所形成的，其中细胞的出生和死亡是同时发生的。给你 m x n 网格面板 board 的当前状态，返回下一个状态。

示例 1： GkpWbCRjioeUI9xZIZzceLllnLd.jpg

输入：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： MFM8b7jOuoHkk0xJSDpcCVRGnQh.jpg

输入：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

题目解析

好的，没问题！我是 AlgoMooc 的算法老师。我们一起来把这个“生命游戏”彻底搞懂，保证零基础也能听得明明白白。

题目在说什么

想象你有一个棋盘，棋盘上每个小格子都是一个“细胞”。细胞有两种状态：活着（用数字 1 表示）或者死了（用数字 0 表示）。

现在，这个棋盘上的细胞们要玩一个“进化游戏”。每个细胞的命运，完全取决于它周围 8个邻居（上、下、左、右、以及四个角）的活细胞数量。规则只有四条，非常简单：

1. 孤独死：如果一个活细胞，它周围的活邻居少于2个，那它下回合就孤独地死掉了。 2. 正好：如果一个活细胞，它周围有2个或3个活邻居，那它下回合就能继续活着。 3. 拥挤死：如果一个活细胞，它周围的活邻居超过3个，那它下回合就因为太拥挤死掉了。 4. 复活：如果一个死细胞，它周围 正好有3个 活邻居，那它下回合就能复活过来。

关键点：所有细胞是 同时 根据“当前”的棋盘状态来决定“下一回合”的状态。你不能先更新一个细胞，再用它更新后的状态去影响另一个细胞。所有变化都是基于同一张“老照片”来计算的。

题目给了你当前的棋盘状态 (board)，让你计算出并返回下一个状态。并且，题目希望你尽量在原地修改，不要用太多的额外空间。

思路是怎么来的

这个问题最直接的想法是：我们复制一份一模一样的棋盘，然后对着原棋盘数邻居，把结果写到新棋盘上。但是，题目希望我们节省空间，尽量在原棋盘上直接改。

这就带来了一个难题：如果你直接把一个细胞从“活”改成了“死”，那它的邻居在数它的时候，就数不到它曾经是“活”的了，结果就全错了。

那怎么办呢？生活里我们怎么解决类似的问题？比如，你有一张名单，上面记录着谁“现在”是好人，谁是坏人。你想根据“现在”的情况，决定他们“将来”是好人还是坏人，并且把结果直接写在名单上，但又不能丢失“现在”的信息。

一个聪明的办法是：用不同的符号来标记。

我们可以这样约定：

• 0：代表“现在是死的，将来也是死的”。
• 1：代表“现在是活的，将来也是活的”。
• 我们额外创造两个临时标记：
• 2：代表“现在是死的，但将来会变成活的”（也就是“复活”）。
• 3：代表“现在是活的，但将来会变成死的”（也就是“死亡”）。

你看，这样一来，当我们第一遍扫描棋盘的时候：

• 如果看到一个格子是 1 或 3，我们就知道它 “现在”是活的。因为 3 虽然将来会死，但它现在还是活的。
• 如果看到一个格子是 0 或 2，我们就知道它 “现在”是死的。因为 2 虽然将来会活，但它现在还是死的。

这样，我们就能在 不丢失“现在”状态信息 的前提下，把“将来”的状态也偷偷地记在同一个格子里了！

等我们把所有格子的“将来”状态都标记好之后，再扫描第二遍，把 2 改成 1（复活），把 3 改成 0（死亡），就大功告成了。这就是整个思路的核心：用额外的状态码来“编码”过去和未来。

代码逐步拆解

现在我们来看代码，每一步都解释清楚。

class Solution {
    public void gameOfLife(int[][] board) {
        // 1. 定义方向
        int[] dx = {-1, 0, 1, -1, 1, -1, 0, 1};
        int[] dy = {-1, -1, -1, 0, 0, 1, 1, 1};
        
        int rows = board.length;
        int cols = board[0].length;

第一步：定义方向

• dx 和 dy 是“方向数组”。一个细胞有8个邻居，我们怎么方便地找到它们呢？我们可以用坐标偏移。
• 比如，dx[0] = -1, dy[0] = -1 代表“左上角”的邻居（行减1，列减1）。
• dx[1] = 0, dy[1] = -1 代表“正上方”的邻居（行不变，列减1）。
• 这样，我们用一个循环 for (int k = 0; k < 8; k++) 就能遍历所有8个方向了。
• rows 和 cols 就是棋盘的行数和列数。

        // 2. 第一遍遍历：根据当前状态，标记未来状态
        for (int i = 0; i < rows; i++) {
            for (int j = 0; j < cols; j++) {
                int neighborLive = 0;
                // 数一数这个细胞周围有多少个“当前”活着的邻居
                for (int k = 0; k < 8; k++) {
                    int x = i + dx[k];
                    int y = j + dy[k];
                    // 检查邻居是否在棋盘内，并且“当前”是活的
                    // 注意：board[x][y] == 1 或 board[x][y] == 3 都代表“当前”是活的！