Cover image for Interview Classic 150 Questions P289 Game of Life

Interview Classic 150 Questions P289 Game of Life

(Updated: )
algorithm
, ,
Timeline

Timeline

2025-11-17

init

Matrix

Title:

P289 Game of Life

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

To save space, we can extend some composite states to include previous states. For example, if a cell’s previous state was 0, but after update it becomes 1, we can define a composite state 2. Then when we see 2, we know both that the cell is currently alive and that it was dead before.

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
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
#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;

		// Up
		if (i > 0) {
			if (board[i - 1][j] == 1) {
				live_cell_cnt++;
			}
		}
		// Down
		if (i < m - 1) {
			if (board[i + 1][j] == 1) {
				live_cell_cnt++;
			}
		}
		// Left
		if (j > 0) {
			if (board[i][j - 1] == 1) {
				live_cell_cnt++;
			}
		}
		//Right
		if (j < n - 1) {
			if (board[i][j + 1] == 1) {
				live_cell_cnt++;
			}
		}
		// Top-left corner
		if (i > 0 && j > 0) {
			if (board[i - 1][j - 1] == 1) {
				live_cell_cnt++;
			}
		}
		// Top-right corner
		if (i > 0 && j < n - 1) {
			if (board[i - 1][j + 1] == 1) {
				live_cell_cnt++;
			}
		}
		// bottom left corner
		if (i < m - 1 && j > 0) {
			if (board[i + 1][j - 1] == 1) {
				live_cell_cnt++;
			}
		}
		// bottom right corner
		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) {
						// If a live cell has fewer than two live neighbors among its eight surrounding positions, it dies;
						board[i][j] = 0;
					} else if (live_cell_cnt == 2 || live_cell_cnt == 3) {
						// If a live cell has two or three live neighbors among its eight surrounding positions, it survives;
						board[i][j] = 1;
					} else {
						// If a live cell has more than three live neighbors among its eight surrounding positions, it dies;
						board[i][j] = 0;
					}
				} else {
					if (live_cell_cnt == 3) {
						// If a dead cell has exactly three live neighbors among its eight surrounding positions, it becomes alive;
						board[i][j] = 1;
					}
				}
			}
		}
	}
};