Interview Classic 150 Questions P289 Game of Life

---

Timeline

Timeline

2025-11-17

init

Matrix

---

Problem:

P289 Game of Life

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

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

#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 the number of live cells in the eight surrounding positions of a live cell is fewer than two, the live cell at that position dies;
						board[i][j] = 0;
					} else if (live_cell_cnt == 2 || live_cell_cnt == 3) {
						// If the number of live cells in the eight surrounding positions of a live cell is two or three, the live cell at that position remains alive;
						board[i][j] = 1;
					} else {
						// If the number of live cells in the eight surrounding positions of a live cell is more than three, the live cell at that position dies;
						board[i][j] = 0;
					}
				} else {
					if (live_cell_cnt == 3) {
						// If the number of live cells in the eight surrounding positions of a dead cell is exactly three, the dead cell at that position revives;
						board[i][j] = 1;
					}
				}
			}
		}
	}
};