力扣289. 生命游戏

2024-01-12 02:28

文章标签 力扣游戏生命 289

本文主要是介绍力扣289. 生命游戏，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

模拟 + 染色

思路：
- 可以复制一个表格，然后根据规则两层循环模拟出结果，但是空间复杂度太高；
- 可以复用原有数组，对其进行染色标记；
  - 最终状态是活的标记值 > 1，还原标记值时可以使用规则 val > 0；
  - 之前是活的现在是死的，标记成 -1，统计活细胞时可以使用规则 abs(val) = 1；
- 根据规则归纳：
  - R1：如果活细胞周围八个位置的活细胞数少于两个，则该位置活细胞死亡，状态由 live 变成 die，用 -1 标记；（原状态是 live，需要被统计成活细胞）
  - R2：如果活细胞周围八个位置有两个或三个活细胞，则该位置活细胞仍然存活，状态没有发生变化；
  - R3：如果活细胞周围八个位置有超过三个活细胞，则该位置活细胞死亡，状态由 live 变成 die，用 -1 标记；（原状态是 live，需要被统计成活细胞）
  - R4：如果死细胞周围正好有三个活细胞，则该位置死细胞复活，状态由 die 变成 live，用 2 标记；（最终状态是 live）
- 进行两次两重循环遍历：
  - 第一次进行染色；
  - 第二次染色还原；

class Solution {
public:void gameOfLife(vector<vector<int>>& board) {int row = board.size();if (0 == row) {return;}int column = board[0].size();if (0 == column) {return;}for (int r = 0; r < row; ++r) {for (int c = 0; c < column; ++c) {int live = 0;// statistics neighborsif (r > 0 && c > 0) {// direct NWif (std::abs(board[r - 1][c - 1]) == 1) {live++;}}if (r > 0) {// direct Nif (std::abs(board[r - 1][c]) == 1) {live++;}                    }if (c > 0) {// direct Wif (std::abs(board[r][c -1]) == 1) {live++;}}if (r + 1 < row) {if (c > 0) {// direct SWif (std::abs(board[r + 1][c - 1]) == 1) {live++;}}// direct Sif (std::abs(board[r + 1][c]) == 1) {live++;}}if (c + 1 < column) {// direct Eif (std::abs(board[r][c + 1]) == 1) {live++;}if (r > 0) {// direct NEif (std::abs(board[r - 1][c + 1]) == 1) {live++;}}// direct SEif (r + 1 < row) {// direct NEif (std::abs(board[r + 1][c + 1]) == 1) {live++;}}}// rule 1 & 3if (board[r][c] == 1 && (live < 2 || live > 3)) {// mark live -> dieboard[r][c] = -1;}// rule 4if (board[r][c] == 0 && live ==  3) {// mark die -> liveboard[r][c] = 2;}}}// recoverfor (int r = 0; r < row; ++r) {for (int c = 0; c < column; ++c) {if (board[r][c] > 0) {board[r][c] = 1;} else {board[r][c] = 0;}}}}
};