面试经典150题 P289 生命游戏

---

时间轴

时间轴

2025-11-17

init

矩阵

---

题目：

P289 生命游戏

https://leetcode.cn/problems/game-of-life/description/?envType=study-plan-v2&envId=top-interview-150

如果要节省空间，可以拓展一些复合状态使其包含之前的状态。举个例子，如果细胞之前的状态是 0，但是在更新之后变成了 1，我们就可以给它定义一个复合状态 2。这样我们看到 2，既能知道目前这个细胞是活的，还能知道它之前是死的。

#include <vector>
using std::vector;

class Solution {
    public:
	void get_cnt(vector<vector<int> > &board, int &live_cell_cnt, int i, int j)
	{
		int m = board.size(), n = board[0].size();
		live_cell_cnt = 0;

		// 上
		if (i > 0) {
			if (board[i - 1][j] == 1) {
				live_cell_cnt++;
			}
		}
		// 下
		if (i < m - 1) {
			if (board[i + 1][j] == 1) {
				live_cell_cnt++;
			}
		}
		// 左
		if (j > 0) {
			if (board[i][j - 1] == 1) {
				live_cell_cnt++;
			}
		}
		//右
		if (j < n - 1) {
			if (board[i][j + 1] == 1) {
				live_cell_cnt++;
			}
		}
		// 左上角
		if (i > 0 && j > 0) {
			if (board[i - 1][j - 1] == 1) {
				live_cell_cnt++;
			}
		}
		// 右上角
		if (i > 0 && j < n - 1) {
			if (board[i - 1][j + 1] == 1) {
				live_cell_cnt++;
			}
		}
		// 左下角
		if (i < m - 1 && j > 0) {
			if (board[i + 1][j - 1] == 1) {
				live_cell_cnt++;
			}
		}
		// 右下角
		if (i < m - 1 && j < n - 1) {
			if (board[i + 1][j + 1] == 1) {
				live_cell_cnt++;
			}
		}
	}
	void gameOfLife(vector<vector<int> > &board)
	{
		vector<vector<int> > original(board);
		int m = board.size(), n = board[0].size();
		int i, j, live_cell_cnt;
		for (i = 0; i < m; i++) {
			for (j = 0; j < n; j++) {
				get_cnt(original, live_cell_cnt, i, j);
				if (original[i][j] == 1) {
					if (live_cell_cnt < 2) {
						// 如果活细胞周围八个位置的活细胞数少于两个，则该位置活细胞死亡；
						board[i][j] = 0;
					} else if (live_cell_cnt == 2 || live_cell_cnt == 3) {
						// 如果活细胞周围八个位置有两个或三个活细胞，则该位置活细胞仍然存活；
						board[i][j] = 1;
					} else {
						// 如果活细胞周围八个位置有超过三个活细胞，则该位置活细胞死亡；
						board[i][j] = 0;
					}
				} else {
					if (live_cell_cnt == 3) {
						// 如果死细胞周围正好有三个活细胞，则该位置死细胞复活；
						board[i][j] = 1;
					}
				}
			}
		}
	}
};