289. 生命游戏

1. 题目

根据 百度百科 ， 生命游戏 ，简称为 生命 ，是英国数学家约翰·何顿·康威在 1970 年发明的细胞自动机。

给定一个包含 m × n 个格子的面板，每一个格子都可以看成是一个细胞。每个细胞都具有一个初始状态： 1 即为 活细胞 （live），或 0 即为 死细胞 （dead）。每个细胞与其八个相邻位置（水平，垂直，对角线）的细胞都遵循以下四条生存定律：

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

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

示例 1：

img

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

img

1
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

进阶：

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

2. 思路

  • 本题提到了需要对每一个单元格中的8个方向进行判断，记录周围八个位置的存活细胞数量，并根据存活细胞数量判断当前单元格的生命状态

  • 由于题目要求采用原地算法进行解决，同时由提示可知，当前单元格中只会有1和0这两个值，以二进制的思路来想，每个单元格在初始状态下只会占用一个二进制位，因此将第二位作为更新后的细胞生命状态

  • 以下是几个核心的二进制算法：

    • 标记更新后的生命状态为存活：currentValue |= 0b10，二进制的第二位为1，采用与的方式来保证标记后的值二进制第二位始终为1，其中1代表的为存活
    • 标记更新后的生命状态为死亡：currentValue |= 0b00，二进制的第二位为0，采用与的方式来标记，其中0代表的是死亡（其实这个算法可以不存在，因为默认第二位就是0，但一切为了可读性）
    • 同时更新面板上的细胞生命状态：由于利用了单元格值的二进制第二位来存储细胞更新后的生命状态，因此我们可以将该位统一向右移动一个（即二进制移位），来达到最终的结果，移位算法为board[row][column] >>= 1

  • 在判断单元格的最终状态时，需要遍历关联8个方向的单元格状态，因此采用的二维数组来替代8个方向，通过直接与当前位置相加能够得到八个方向的下标

image-20230825011853277

3. 代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
class Solution {
    public void gameOfLife(int[][] board) {
        var rows = board.length;
        var columns = board[0].length;

        for (var i = 0; i < rows; ++i) {
            for (var j = 0; j < columns; ++j) {
                if (isAlive(board, i, j)) {
                    markLive(board, i, j);
                } else {
                    markDead(board, i, j);
                }
            }
        }

        for (var i = 0; i < rows; ++i) {
            for (var j = 0; j < columns; ++j) {
                offsetBitAsResult(board, i, j);
            }
        }
    }

    private void offsetBitAsResult(int[][] board, int row, int col) {
        board[row][col] >>= 1;
    }

    private boolean isAlive(int[][] board, int row, int col) {
        int[][] directions = {{-1, -1}, {-1, 0}, {-1, 1}, {0, -1}, {0, 1}, {1, -1}, {1, 0}, {1, 1}};
        var aliveCount = 0;
        var isCurrentAlive = isCurrentAlive(board, row, col);

        for (var i = 0; i < directions.length; ++i) {
            var direction = directions[i];
            var nextRow = row + direction[0];
            var nextCol = col + direction[1];
            if (isValid(board, nextRow, nextCol) && isCurrentAlive(board, nextRow, nextCol)) {
                aliveCount++;
            }
        }
        
        if (isCurrentAlive && (aliveCount < 2 || aliveCount > 3)) {
            return false;
        }

        if (!isCurrentAlive && aliveCount != 3) {
            return false;
        }

        return true;
    }

    private boolean isCurrentAlive(int[][] board, int row, int column) {
        return (board[row][column] & 1) == 1;
    }

    private void markLive(int[][] board, int row, int column) {
        board[row][column] |= (0b10);
    }

    private void markDead(int[][] board, int row, int column) {
        board[row][column] |= (0b00);
    }

    private boolean isValid(int[][] board, int row, int column) {
        var rows = board.length;
        var columns = board[0].length;

        return row >= 0 && row < rows && column >= 0 && column < columns;
    }
}

4. 复杂度

  • 时间复杂度：O(mn)
  • 空间复杂度：O(1)

image-20230825004854524