每日算法系列【LeetCode 289】生命游戏

题目描述

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

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

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

根据当前状态，写一个函数来计算面板上细胞的下一个（一次更新后的）状态。下一个状态是通过将上述规则同时应用于当前状态下的每个细胞所形成的，其中细胞的出生和死亡是同时发生的。

示例1

        输入：
[
  [0,1,0],
  [0,0,1],
  [1,1,1],
  [0,0,0]
]
输出：
[
  [0,0,0],
  [1,0,1],
  [0,1,1],
  [0,1,0]
]

进阶

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

题解

这题要求你根据数组每个元素四周的状态来更新数组元素。如果使用一个辅助数组，遍历原数组，然后保存更新后的状态到辅助数组里。这样的话轻轻松松，没有任何难度。但是这题意思是让你不使用辅助数组，直接修改原数组元素，达到一样的目的。

这样的话就不能直接修改原数组元素了，不然当你遍历下一个元素的时候，它周围的值都变掉了，还怎么看它要不要变呢？所以我们应该想办法把变化前变化后的元素都保存下来。

因为这题只有两个状态 0 和 1 ，所以我们可以用两位二进制来表示变化前和后的状态，第一位表示变化后，第二位表示变化前。 00，10，01，11 分别表示 0 不变、0 变到 1 、1 变到 0 、1 不变四种变化情况。这样的话就算你直接修改了元素值，也能获取到它的原来的值。最后只需要进行第二遍扫描，取出变化后的值，也就是第一位就行了。

判断和修改都可以通过位运算来完成。判断修改前是否为 1 可以通过 $x\&1$ 来看。用 m 表示修改（1）或者不修改（0），那么更新后元素就变成了 $x + (m << 1)$ 。最后更新后的数组元素就是 $x >> 1$ 了。

而边界问题很好处理，只需要判断一下有没有超出边界就行了。

代码

c++

        class Solution {
public:
    void gameOfLife(vector<vector<int>>& board) {
        int dx[] = {-1, -1, -1, 0, 1, 1, 1, 0};
        int dy[] = {-1, 0, 1, 1, 1, 0, -1, -1};
        int n = board.size(), m = board[0].size();
        for (int x = 0; x < n; ++x) {
            for (int y = 0; y < m; ++y) {
                int cnt = 0;
                for (int i = 0; i < 8; ++i) {
                    int nx = x + dx[i], ny = y + dy[i];
                    if (0 <= nx && nx < n && 0 <= ny && ny < m && (board[nx][ny]&1)) {
                        cnt++;
                    }
                }
                if (board[x][y] == 1) {
                    board[x][y] += ((cnt == 2 || cnt == 3) << 1);
                } else {
                    board[x][y] += ((cnt == 3) << 1);
                }
            }
        }
        for (int x = 0; x < n; ++x) {
            for (int y = 0; y < m; ++y) {
                board[x][y] >>= 1;
            }
        }
    }
};

python

        class Solution:
    def gameOfLife(self, board: List[List[int]]) -> None:
        dx = [-1, -1, -1, 0, 1, 1, 1, 0]
        dy = [-1, 0, 1, 1, 1, 0, -1, -1]
        n, m = len(board), len(board[0])
        for x in range(n):
            for y in range(m):
                cnt = 0
                for i in range(8):
                    nx, ny = x + dx[i], y + dy[i]
                    if 0 <= nx < n and 0 <= ny < m and (board[nx][ny]&1) != 0:
                        cnt += 1
                if board[x][y] == 1:
                    board[x][y] += ((1 if cnt==2 or cnt==3 else 0) << 1)
                else:
                    board[x][y] += ((1 if cnt==3 else 0) << 1)
        for x in range(n):
            for y in range(m):
                board[x][y] >>= 1