文章目录
1. 题目来源
链接：289. 生命游戏
来源：LeetCode
2. 题目说明
3. 题目解析
方法一：编码+常规解法
由于题目中要求用原地算法来解题，所以就不能新建一个相同大小的数组，那么只能更新原有数组。题目中要求所有的位置必须被同时更新，但在循环程序中还是一个位置一个位置更新的，当一个位置更新了，这个位置成为其他位置的邻居时，怎么知道其未更新的状态呢？可以使用编码及状态机转换：
0 : 上一轮是0，这一轮过后还是0
1 : 上一轮是1，这一轮过后还是1
2 : 上一轮是1，这一轮过后变为0
3 : 上一轮是0，这一轮过后变为1
最后对所有状态对 2 取余，则状态 0 和 2 就变成死细胞，状态 1 和 3 就是活细胞，达成目的。
先对原数组进行逐个扫描，对于每一个位置，扫描其周围八个位置，如果遇到状态 1 或 2，就计数器累加 1，扫完 8 个邻居，如果少于两个活细胞或者大于三个活细胞，而且当前位置是活细胞的话，标记状态 2，如果正好有三个活细胞且当前是死细胞的话，标记状态 3。完成一遍扫描后再对数据扫描一遍，对 2 取余变成我们想要的结果。
参见代码如下：
// 执行用时 :0 ms, 在所有 C++ 提交中击败了100.00%的用户
// 内存消耗 :7 MB, 在所有 C++ 提交中击败了100.00%的用户
class Solution {
public:
void gameOfLife(vector<vector<int>>& board) {
int m = board.size(), n = board[0].size();
int dx[] = {-1, -1, -1, 0, 1, 1, 1, 0};
int dy[] = {-1, 0, 1, 1, 1, 0, -1, -1};
for (int i = 0; i < m; ++i) {
for (int j = 0; j < n; ++j) {
int cnt = 0;
for (int k = 0; k < 8; ++k) {
int x = i + dx[k];
int y = j + dy[k];
if (x >= 0 and x < m and y >= 0 and y < n and (board[x][y] == 1 or board[x][y] == 2))
++cnt;
}
if (board[i][j] and (cnt < 2 or cnt > 3)) board[i][j] = 2;
else if (!board[i][j] and cnt == 3) board[i][j] = 3;
}
}
for (int i = 0; i < m; ++i) {
for (int j = 0; j < n; ++j) {
board[i][j] %= 2;
}
}
}
};