生命游戏：一个经典的细胞自动机问题详解

生命游戏：一个经典的细胞自动机问题详解

生命游戏是一个由英国数学家约翰·何顿·康威在1970年发明的细胞自动机，它通过简单的规则展现了复杂的生命演化过程。在这个游戏中，一个二维网格上的每个细胞根据其周围八个邻居的状态，遵循特定的生存定律进行状态更新。本文将详细介绍生命游戏的规则、解题思路和具体实现代码。

生命游戏，简称为生命，是英国数学家约翰·何顿·康威在1970年发明的细胞自动机。给定一个包含m×n个格子的面板，每一个格子都可以看成是一个细胞。每个细胞都具有一个初始状态：1即为活细胞（live），或0即为死细胞（dead）。每个细胞与其八个相邻位置（水平，垂直，对角线）的细胞都遵循以下四条生存定律：

1. 如果活细胞周围八个位置的活细胞数少于两个，则该位置活细胞死亡；
2. 如果活细胞周围八个位置有两个或三个活细胞，则该位置活细胞仍然存活；
3. 如果活细胞周围八个位置有超过三个活细胞，则该位置活细胞死亡；
4. 如果死细胞周围正好有三个活细胞，则该位置死细胞复活；

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

思路：

这个问题的关键是如何在不影响其他细胞状态的情况下，计算每个细胞的新状态。我们需要采取一种策略，在计算过程中避免直接修改当前状态，造成无法预料的影响。

为了实现这个思路，通常有两个步骤：

1. 先计算出所有细胞的未来状态，但不立即更新棋盘的状态，而是用一个临时值来标记细胞的未来状态。
2. 遍历整个棋盘，最终更新所有细胞的状态。

在代码中，我们用-1和2作为临时标记来表示将要改变的状态：

• -1：表示当前是活细胞（1），但是在下一代将会死。
• 2：表示当前是死细胞（0），但是在下一代将会复活。

详细解释代码思路

1. 邻居的遍历：

• 每个细胞有8个邻居。为了计算一个细胞周围的活邻居数量，我们可以遍历该细胞周围的8个方向，统计有多少个邻居是活细胞。
• 我们用neighbors = {-1, 0, 1}来表示相邻的位置，分别表示上、下、左、右以及四个对角线方向。通过遍历这些方向，可以获取每个细胞的8个邻居的坐标。

2. 规则判断和临时标记：

• 对于每个细胞，首先计算它周围活细胞的数量liveNeighbors。
• 然后，根据以下规则来决定细胞的下一代状态：
• 规则 1：如果细胞当前是活的（board[row][col] == 1），且它周围的活邻居小于2或者大于3（即“孤独”或者“过度拥挤”），则该细胞会死。因此，我们将其标记为-1，表示它将会死。
• 规则 2：如果细胞当前是死的（board[row][col] == 0），且它周围有恰好3个活邻居（即“繁殖”），则该细胞将复活。因此，我们将其标记为2，表示它将会活。
• 规则 3：如果细胞当前是活的，并且它周围的活邻居数量正好为2或3，那么它将继续存活，因此不需要标记。

3. 更新棋盘状态：

• 一旦我们遍历完所有的细胞并根据规则标记了它们的状态，接下来就要更新棋盘了。
• 在这一阶段，我们将所有-1转换为0（死细胞），将所有2转换为1（活细胞）。这样，我们就完成了所有细胞的状态更新。

步骤总结

1. 遍历每个细胞，并计算该细胞周围的活邻居数量。
2. 根据生命游戏规则，对每个细胞做出改变，使用临时标记-1和2来表示即将发生的状态变化。
3. 遍历棋盘一次，将临时标记转换为实际的状态（即-1转换为0，2转换为1）。

优点与难点

• 避免直接修改原始状态：通过使用临时标记（-1和2），避免了直接修改原始状态对其他细胞产生不必要的影响。
• 时间复杂度：该算法的时间复杂度是O(m * n)，其中m和n分别是棋盘的行数和列数，因为每个细胞都需要被访问一次，且每个细胞有固定的邻居数量（8个）。

class Solution {
    public void gameOfLife(int[][] board) {
        int[] neighbors = {-1, 0, 1};
        int rows = board.length;
        int cols = board[0].length;
        for(int row = 0; row < rows; row++){
            for(int col = 0; col < cols; col++){
                // 对于每一个细胞统计其八个相邻位置里的活细胞数量
                int liveNeighbors = 0;
                for(int i = 0; i < 3; i++){
                    for(int j = 0; j <3; j++){
                        //避免自己本身的细胞被计数
                        if(!(neighbors[i] == 0 && neighbors[j] == 0)){
                            //相邻位置的坐标
                            //当 i = -1 和 j = 1 时，r = row - 1，c = col + 1，即左上方的邻居。
                            //当 i = 1 和 j = 0 时，r = row + 1，c = col，即下方的邻居。
                            int r = (row + neighbors[i]);
                            int c = (col + neighbors[j]);
                            //查看相邻的细胞是否是活细胞 + 边界检查
                            if((r < rows && r >= 0) && (c < cols && c >= 0) && (Math.abs(board[r][c]) == 1)){
                                liveNeighbors++;
                            }
                        }
                    }
                }
                //规则1 或 规则3
                if((board[row][col] == 1) && (liveNeighbors < 2 || liveNeighbors > 3)){
                    //-1表示过去是活的，现在是死的
                    board[row][col] = -1;
                }
                //规则4
                if(board[row][col] == 0 && liveNeighbors == 3){
                    //2表示过去是死的，现在是活的
                    board[row][col] = 2;
                }
            }
        }
        //整体遍历一遍更新状态
        for(int row = 0; row < rows; row++){
            for(int col = 0; col < cols; col++){
                if(board[row][col] > 0){
                    board[row][col] = 1;
                }else{
                    board[row][col] = 0;
                }
            }
        }
    }
}