生命游戏
· 阅读需 7 分钟
力扣面试经典——289题
💡 参考代码：
/**
* 根据生命游戏规则更新面板状态
* @param board 二维数组表示的面板
* @param boardSize 行数 m
* @param boardColSize 每行的列数数组
*/
void gameOfLife(int** board, int boardSize, int* boardColSize){
// 边界检查
if (board == NULL || boardSize == 0 || boardColSize == NULL) {
return;
}
int rows = boardSize;
int cols = boardColSize[0];
// 八个方向的偏移量：上下左右和四个对角线
int directions[8][2] = {
{-1, -1}, {-1, 0}, {-1, 1}, // 上方三个位置
{0, -1}, {0, 1}, // 左右两个位置
{1, -1}, {1, 0}, {1, 1} // 下方三个位置
};
// 第一次遍历：计算每个细胞周围的活细胞数量，并用状态标记记录变化
// 状态标记：
// 0 -> 0: 仍然死亡，保持0
// 1 -> 1: 仍然存活，保持1
// 0 -> 1: 死亡变存活，标记为2
// 1 -> 0: 存活变死亡，标记为3
for (int i = 0; i < rows; i++) {
for (int j = 0; j < cols; j++) {
int liveNeighbors = 0; // 统计活细胞邻居数量
// 检查8个方向的邻居
for (int k = 0; k < 8; k++) {
int newRow = i + directions[k][0];
int newCol = j + directions[k][1];
// 检查边界并统计活细胞（原始状态为1或状态3表示原来是活的）
if (newRow >= 0 && newRow < rows &&
newCol >= 0 && newCol < cols &&
(board[newRow][newCol] == 1 || board[newRow][newCol] == 3)) {
liveNeighbors++;
}
}
// 应用生命游戏规则
if (board[i][j] == 1) {
// 当前是活细胞
if (liveNeighbors < 2 || liveNeighbors > 3) {
// 规则1和3：活细胞死亡
board[i][j] = 3; // 标记为从活到死
}
// 规则2：活细胞仍然存活，无需改变状态
} else {
// 当前是死细胞
if (liveNeighbors == 3) {
// 规则4：死细胞复活
board[i][j] = 2; // 标记为从死到活
}
// 其他情况保持死亡状态
}
}
}
// 第二次遍历：根据状态标记更新最终状态
for (int i = 0; i < rows; i++) {
for (int j = 0; j < cols; j++) {
if (board[i][j] == 2) {
// 死到活
board[i][j] = 1;
} else if (board[i][j] == 3) {
// 活到死
board[i][j] = 0;
}
// 状态0和1保持不变
}
}
}
📖 总结：
点击展开题目总结
🤔 生命游戏
1️⃣ 题目核心信息
🎯 功能描述：根据康威生命游戏的四条生存定律，同时更新整个细胞面板的状态
📥 输入输出：
- 输入：
board- 二维整数数组，表示当前细胞面板状态（0表示死细胞，1表示活细胞） - 输出：无返回值，直接修改输入的
board数组为下一状态
2️⃣ 实现原理
💡 核心思路：使用原地算法，通过引入中间状态码来同时记录原始状态和新状态，避免更新过程中的相互影响
📋 实现步骤：
- 定义八个方向的偏移量数组，用于检查每个细胞的邻居
- 第一次遍历面板，统计每个细胞周围活细胞数量并根据规则标记中间状态
- 使用状态码2表示死细胞变活细胞，状态码3表示活细胞变死细胞
- 第二次遍历面板，将中间状态转换为最终状态
3️⃣ 关键点解析
🎯 代码技巧
- 状态编码：使用2和3作为中间状态，既保留原始信息又标记变化
- 方向数组：预定义8个方向的偏移量，简化邻居检查逻辑
- 边界判断：在检查邻居时进行边界验证，避免数组越界
- 原地修改：不使用额外空间，满足进阶要求
4️⃣ 使用场景
✅ 适用情况：
- 细胞自动机模拟
- 并行状态更新问题
- 需要原地算法优化空间的场景
⚠️ 前提条件：
- 输入矩阵不为空
- 矩阵元素只能是0或1
- 所有细胞状态需要同时更新
5️⃣ 复杂度分析
-
⏱️ 时间复杂度：O(m×n)，其中m和n分别是面板的行数和列数，需要遍历每个细胞两次
-
💾 空间复杂度：O(1)，只使用了常数额外空间，满足原地算法要求
6️⃣ 注意事项
🚩 边界情况：
- 空矩阵或NULL指针
- 单行或单列矩阵
- 矩阵边缘细胞的邻居检查
💥 易错点：
- 忘记同时更新所有细胞，导致状态依赖错误
- 统计邻居时未正确识别中间状态
- 边界检查不完整导致数组越界
- 状态转换时混淆原始状态和新状态
7️⃣ 补充说明
🔁 执行过程详解
第一步：第一次遍历 - 统计邻居并标记状态
我们逐个检查每个细胞：
细胞 [0,0] (值: 0)
- 周围活细胞数: 1个 ([0,1])
- 规则4不满足(需要恰好3个)，保持死亡
- 状态保持: 0
细胞 [0,1] (值: 1)
- 周围活细胞数: 1个 ([1,1])
- 规则1满足(少于2个)，将死亡
- 状态标记: 3
细胞 [0,2] (值: 0)
- 周围活细胞数: 1个 ([1,1])
- 规则4不满足(需要恰好3个)，保持死亡
- 状态保持: 0
细胞 [1,0] (值: 0)
- 周围活细胞数: 2个 ([0,1], [2,1])
- 规则4不满足(需要恰好3个)，保持死亡
- 状态保持: 0
细胞 [1,1] (值: 1)
- 周围活细胞数: 2个 ([0,1], [2,1])
- 规则2满足(2或3个)，保持存活
- 状态保持: 1
细胞 [1,2] (值: 0)
- 周围活细胞数: 2个 ([0,1], [2,1])
- 规则4不满足(需要恰好3个)，保持死亡
- 状态保持: 0
细胞 [2,0] (值: 0)
- 周围活细胞数: 1个 ([1,1])
- 规则4不满足(需要恰好3个)，保持死亡
- 状态保持: 0
细胞 [2,1] (值: 1)
- 周围活细胞数: 1个 ([1,1])
- 规则1满足(少于2个)，将死亡
- 状态标记: 3
细胞 [2,2] (值: 0)
- 周围活细胞数: 1个 ([1,1])
- 规则4不满足(需要恰好3个)，保持死亡
- 状态保持: 0
第一次遍历后状态：
中间状态: [0, 3, 0] [0, 1, 0] [0, 3, 0]
第二步：第二次遍历 - 更新最终状态
根据中间状态码更新最终状态：
- 状态3 → 0 (活细胞变死细胞)
- 状态1 → 1 (保持活细胞)
- 状态0 → 0 (保持死细胞)
最终结果：
下一状态: [0, 0, 0] [0, 1, 0] [0, 0, 0]
📊 状态转换图解
初始状态 中间状态 最终状态
[0, 1, 0] ---> [0, 3, 0] ---> [0, 0, 0]
[0, 1, 0] ---> [0, 1, 0] ---> [0, 1, 0]
[0, 1, 0] ---> [0, 3, 0] ---> [0, 0, 0]
│ │ │
│ │ └── 活细胞减少，只剩中心一个
│ └── 标记将要死亡的细胞(3)和保持的细胞(1)
└── 垂直排列的3个活细胞
🧠 关键理解点
- 同时更新：所有细胞的状态是基于同一初始状态计算的
- 状态标记：使用中间状态码避免更新过程中的相互影响
- 邻居统计：在统计邻居时，状态3仍被视为活细胞(原始状态)
- 边界处理：边缘细胞的邻居数量自然减少
这个例子展示了垂直线状的活细胞如何在生命游戏规则下演变为只剩中心一个活细胞的稳定状态。
加载评论中...