289 生命游戏

题目描述#

给定一个 m x n 的二维面板，1 表示活细胞，0 表示死细胞。每个细胞都要根据周围八个方向的活细胞数量，按照题目的四条规则决定下一轮状态。

关键点在于：所有细胞的出生和死亡是同时发生的。所以在更新某个位置时，不能让它提前影响其他位置的判断。

题目要求直接在原数组 board 上完成更新，不需要返回值。

思路#

这题的难点不是规则本身，而是“原地更新”和“同时生效”要同时满足。如果一边遍历一边直接把 1 改成 0，或者把 0 改成 1，后面再统计邻居时就会把已经修改过的结果当成原始状态，导致判断出错。

一个常见做法是再开一个同样大小的矩阵保存下一轮状态，但这题要求直接修改原矩阵，所以这里用了“中间状态标记”的方式：

2 表示这个位置原来是活细胞，现在会死
3 表示这个位置原来是死细胞，现在会活

这样第一遍扫描时，虽然数组内容被改了，但仍然可以区分“原来是否活着”：

1 代表原来活
2 也代表原来活，只是下一轮会死

所以在统计某个格子周围活细胞数量时，只要把 1 和 2 都算作原来的活细胞即可。

具体分两遍处理：

第一遍先遍历整个矩阵。对每个位置统计周围原始活细胞数量，然后按题目规则打标记：

活细胞如果邻居少于 2 或多于 3，就标成 2
死细胞如果邻居恰好等于 3，就标成 3

第二遍再统一把中间状态还原成最终答案：

2 -> 0
3 -> 1

这样既保留了原始状态供后续统计邻居使用，又满足了原地更新的要求。时间复杂度是 O(mn)，因为矩阵被遍历了两次；额外空间复杂度是 O(1)，只用了常数级辅助变量。

代码#

func gameOfLife(board [][]int) {
	rows := len(board)
	if rows == 0 {
		return
	}
	cols := len(board[0])

	// 统计某个格子周围活细胞的数量（原来的状态）
	countLiveNeighbors := func(r, c int) int {
		count := 0
		for dr := -1; dr <= 1; dr++ {
			for dc := -1; dc <= 1; dc++ {
				if dr == 0 && dc == 0 {
					continue
				}
				nr, nc := r+dr, c+dc
				if nr >= 0 && nr < rows && nc >= 0 && nc < cols {
					// 2 表示"原来活、现在死"，也要计入
					if board[nr][nc] == 1 || board[nr][nc] == 2 {
						count++
					}
				}
			}
		}
		return count
	}

	// 第一遍：标记状态变化
	for r := 0; r < rows; r++ {
		for c := 0; c < cols; c++ {
			live := countLiveNeighbors(r, c)
			if board[r][c] == 1 {
				// 活细胞：邻居不是2或3个 → 死亡
				if live < 2 || live > 3 {
					board[r][c] = 2 // 原来活，现在死
				}
			} else {
				// 死细胞：邻居恰好3个 → 复活
				if live == 3 {
					board[r][c] = 3 // 原来死，现在活
				}
			}
		}
	}

	// 第二遍：统一映射回 0/1
	for r := 0; r < rows; r++ {
		for c := 0; c < cols; c++ {
			if board[r][c] == 2 {
				board[r][c] = 0
			} else if board[r][c] == 3 {
				board[r][c] = 1
			}
		}
	}
}