289. 生命游戏

题目描述

生命游戏是数学家康威于 1970 年提出的一种细胞自动机。输入一个 m x n 的网格 board，每个格子是一个细胞：1 表示活着，0 表示死亡。

每个细胞有八个邻居（上下左右和四个斜角，超出网格的位置不算）。下一时刻每个细胞的状态按如下规则决定：活细胞的活邻居少于 2 个时死去；有 2 个或 3 个时继续活着；多于 3 个时死去。死细胞的活邻居正好是 3 个时变成活细胞，否则仍然是死的。

所有细胞依据当前状态同时变化，不能用某些格子的新值去计算其他格子。

请直接把 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]]

解释：右下角的死细胞恰好有 3 个活邻居，因此复活；另外三个活细胞各有 2 个活邻居，继续存活。

数据范围

m == board.length
n == board[i].length
1 <= m, n <= 25
board[i][j] 只会是 0 或 1。

进阶：能否原地完成更新，同时保证所有格子是同时变化的？另外，这里用二维数组表示网格，但理论上网格是无限大的，活细胞扩展到数组边界时会出问题，你会如何处理？

解题思路：原地位编码

难点在于“同时更新”：如果直接改写一个格子，后面的邻居统计就会读到新状态。用两个二进制位：第 0 位存当前状态，第 1 位存下一状态。第一遍只用 & 1 读当前状态、统计八邻域活细胞数，若下一状态为活就把第 1 位置 1；第二遍把每个格子右移一位，就得到新状态。

为什么正确

第一遍中，任何格子的 board & 1 始终是原始状态。

复杂度分析

时间 O(mn)（每格看 8 个邻居），额外空间 O(1)。

易错点

不能边统计边改写 0/1，否则后面的格子会看到已更新的邻居。统计时要用 & 1 而不是直接判断非 0，并要排除自己、处理好边界。

参考代码

Python、Java、C++、Go、JavaScript、TypeScript 六种语言，逻辑一致。

class Solution:
    def gameOfLife(self, board: List[List[int]]) -> None:
        m, n = len(board), len(board[0])
        for i in range(m):
            for j in range(n):
                live = 0
                for x in range(max(0, i - 1), min(m, i + 2)):
                    for y in range(max(0, j - 1), min(n, j + 2)):
                        if (x, y) != (i, j) and board[x][y] & 1:
                            live += 1
                if board[i][j] & 1 and live in (2, 3):
                    board[i][j] |= 2
                elif not board[i][j] & 1 and live == 3:
                    board[i][j] |= 2
        for i in range(m):
            for j in range(n):
                board[i][j] >>= 1

class Solution {
    public void gameOfLife(int[][] board) {
        int m = board.length, n = board[0].length;
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                int live = 0;
                for (int x = Math.max(0, i - 1); x < Math.min(m, i + 2); x++) {
                    for (int y = Math.max(0, j - 1); y < Math.min(n, j + 2); y++) {
                        if ((x != i || y != j) && (board[x][y] & 1) != 0) {
                            live++;
                        }
                    }
                }
                if ((board[i][j] & 1) != 0 && (live == 2 || live == 3)) {
                    board[i][j] |= 2;
                } else if ((board[i][j] & 1) == 0 && live == 3) {
                    board[i][j] |= 2;
                }
            }
        }
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                board[i][j] >>= 1;
            }
        }
    }
}

class Solution {
public:
    void gameOfLife(vector<vector<int>>& board) {
        int m = board.size(), n = board[0].size();
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                int live = 0;
                for (int x = max(0, i - 1); x < min(m, i + 2); x++) {
                    for (int y = max(0, j - 1); y < min(n, j + 2); y++) {
                        if ((x != i || y != j) && (board[x][y] & 1)) {
                            live++;
                        }
                    }
                }
                if ((board[i][j] & 1) && (live == 2 || live == 3)) {
                    board[i][j] |= 2;
                } else if (!(board[i][j] & 1) && live == 3) {
                    board[i][j] |= 2;
                }
            }
        }
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                board[i][j] >>= 1;
            }
        }
    }
};

func gameOfLife(board [][]int) {
	m, n := len(board), len(board[0])
	for i := 0; i < m; i++ {
		for j := 0; j < n; j++ {
			live := 0
			for x := max(0, i-1); x < min(m, i+2); x++ {
				for y := max(0, j-1); y < min(n, j+2); y++ {
					if (x != i || y != j) && board[x][y]&1 == 1 {
						live++
					}
				}
			}
			if board[i][j]&1 == 1 && (live == 2 || live == 3) {
				board[i][j] |= 2
			} else if board[i][j]&1 == 0 && live == 3 {
				board[i][j] |= 2
			}
		}
	}
	for i := 0; i < m; i++ {
		for j := 0; j < n; j++ {
			board[i][j] >>= 1
		}
	}
}

var gameOfLife = function(board) {
    const m = board.length, n = board[0].length;
    for (let i = 0; i < m; i++) {
        for (let j = 0; j < n; j++) {
            let live = 0;
            for (let x = Math.max(0, i - 1); x < Math.min(m, i + 2); x++) {
                for (let y = Math.max(0, j - 1); y < Math.min(n, j + 2); y++) {
                    if ((x != i || y != j) && (board[x][y] & 1)) {
                        live++;
                    }
                }
            }
            if ((board[i][j] & 1) && (live == 2 || live == 3)) {
                board[i][j] |= 2;
            } else if (!(board[i][j] & 1) && live == 3) {
                board[i][j] |= 2;
            }
        }
    }
    for (let i = 0; i < m; i++) {
        for (let j = 0; j < n; j++) {
            board[i][j] >>= 1;
        }
    }
};

function gameOfLife(board: number[][]): void {
    const m = board.length, n = board[0].length;
    for (let i = 0; i < m; i++) {
        for (let j = 0; j < n; j++) {
            let live = 0;
            for (let x = Math.max(0, i - 1); x < Math.min(m, i + 2); x++) {
                for (let y = Math.max(0, j - 1); y < Math.min(n, j + 2); y++) {
                    if ((x != i || y != j) && (board[x][y] & 1)) {
                        live++;
                    }
                }
            }
            if ((board[i][j] & 1) && (live == 2 || live == 3)) {
                board[i][j] |= 2;
            } else if (!(board[i][j] & 1) && live == 3) {
                board[i][j] |= 2;
            }
        }
    }
    for (let i = 0; i < m; i++) {
        for (let j = 0; j < n; j++) {
            board[i][j] >>= 1;
        }
    }
}

载入编辑器，自己跑一遍 →

其他解法

问题的关键是“更新时还要读到旧状态”。复制数组用一份副本保存旧状态；原地位编码用最低位存旧状态、次低位存新状态，最后统一右移，省掉了副本。

解法 2：复制原数组时间 O(mn)，空间 O(mn)

先把整块面板复制一份。统计邻居时只看副本，把新状态直接写回原面板。副本始终是旧状态，所以更新顺序不影响结果。

最直白，不需要编码技巧。需要 O(mn) 额外空间，不满足进阶的原地要求。

class Solution:
    def gameOfLife(self, board: List[List[int]]) -> None:
        m, n = len(board), len(board[0])
        old = [row[:] for row in board]
        for i in range(m):
            for j in range(n):
                live = 0
                for x in range(max(0, i - 1), min(m, i + 2)):
                    for y in range(max(0, j - 1), min(n, j + 2)):
                        if (x, y) != (i, j):
                            live += old[x][y]
                if old[i][j] == 1:
                    board[i][j] = 1 if live in (2, 3) else 0
                else:
                    board[i][j] = 1 if live == 3 else 0

class Solution {
    public void gameOfLife(int[][] board) {
        int m = board.length, n = board[0].length;
        int[][] old = new int[m][];
        for (int i = 0; i < m; i++) old[i] = board[i].clone();
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                int live = 0;
                for (int x = Math.max(0, i - 1); x < Math.min(m, i + 2); x++)
                    for (int y = Math.max(0, j - 1); y < Math.min(n, j + 2); y++)
                        if (x != i || y != j) live += old[x][y];
                if (old[i][j] == 1) board[i][j] = (live == 2 || live == 3) ? 1 : 0;
                else board[i][j] = live == 3 ? 1 : 0;
            }
        }
    }
}

class Solution {
public:
    void gameOfLife(vector<vector<int>>& board) {
        int m = board.size(), n = board[0].size();
        vector<vector<int>> old = board;
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                int live = 0;
                for (int x = max(0, i - 1); x < min(m, i + 2); x++)
                    for (int y = max(0, j - 1); y < min(n, j + 2); y++)
                        if (x != i || y != j) live += old[x][y];
                if (old[i][j] == 1) board[i][j] = (live == 2 || live == 3) ? 1 : 0;
                else board[i][j] = live == 3 ? 1 : 0;
            }
        }
    }
};

func gameOfLife(board [][]int) {
	m, n := len(board), len(board[0])
	old := make([][]int, m)
	for i := range board {
		old[i] = append([]int(nil), board[i]...)
	}
	for i := 0; i < m; i++ {
		for j := 0; j < n; j++ {
			live := 0
			for x := max(0, i-1); x < min(m, i+2); x++ {
				for y := max(0, j-1); y < min(n, j+2); y++ {
					if x != i || y != j {
						live += old[x][y]
					}
				}
			}
			if old[i][j] == 1 && (live == 2 || live == 3) || old[i][j] == 0 && live == 3 {
				board[i][j] = 1
			} else {
				board[i][j] = 0
			}
		}
	}
}

var gameOfLife = function(board) {
    const m = board.length, n = board[0].length;
    const old = board.map(row => row.slice());
    for (let i = 0; i < m; i++) {
        for (let j = 0; j < n; j++) {
            let live = 0;
            for (let x = Math.max(0, i - 1); x < Math.min(m, i + 2); x++)
                for (let y = Math.max(0, j - 1); y < Math.min(n, j + 2); y++)
                    if (x !== i || y !== j) live += old[x][y];
            if (old[i][j] === 1) board[i][j] = (live === 2 || live === 3) ? 1 : 0;
            else board[i][j] = live === 3 ? 1 : 0;
        }
    }
};

function gameOfLife(board: number[][]): void {
    const m = board.length, n = board[0].length;
    const old = board.map(row => row.slice());
    for (let i = 0; i < m; i++) {
        for (let j = 0; j < n; j++) {
            let live = 0;
            for (let x = Math.max(0, i - 1); x < Math.min(m, i + 2); x++)
                for (let y = Math.max(0, j - 1); y < Math.min(n, j + 2); y++)
                    if (x !== i || y !== j) live += old[x][y];
            if (old[i][j] === 1) board[i][j] = (live === 2 || live === 3) ? 1 : 0;
            else board[i][j] = live === 3 ? 1 : 0;
        }
    }
}

数学专题的其他题目

查看数学全部题目 →