CC BY 4.0 （除特别声明或转载文章外）
如果这篇博客帮助到你，可以请我喝一杯咖啡~
题目
289. 生命游戏
难度中等
根据 百度百科 ，生命游戏，简称为生命，是英国数学家约翰·何顿·康威在 1970 年发明的细胞自动机。
给定一个包含 m × n 个格子的面板，每一个格子都可以看成是一个细胞。每个细胞都具有一个初始状态：1 即为活细胞（live），或 0 即为死细胞（dead）。每个细胞与其八个相邻位置（水平，垂直，对角线）的细胞都遵循以下四条生存定律：
- 如果活细胞周围八个位置的活细胞数少于两个，则该位置活细胞死亡；
- 如果活细胞周围八个位置有两个或三个活细胞，则该位置活细胞仍然存活；
- 如果活细胞周围八个位置有超过三个活细胞，则该位置活细胞死亡；
- 如果死细胞周围正好有三个活细胞，则该位置死细胞复活；
根据当前状态，写一个函数来计算面板上所有细胞的下一个（一次更新后的）状态。下一个状态是通过将上述规则同时应用于当前状态下的每个细胞所形成的，其中细胞的出生和死亡是同时发生的。
解法
这题使用状态拓展，时间复杂度O(2mn), 空间复杂度O(1).
class Solution {
public:
int count(int x,int y,vector<vector<int>>& board){
int ans = 0;
for(int i=0;i<8;++i){
int xx = x+dx[i];
int yy = y+dy[i];
if (!(xx<0 || yy<0 || xx>=board.size() || yy >= board[0].size())){
if(abs(board[xx][yy]) == 1 ){
ans++;
}
}
}
return ans;
}
void gameOfLife(vector<vector<int>>& board) {
//vector<vector<int>> temp = board;
for(int i=0;i<board.size();++i){
for(int j=0;j<board[i].size();++j){
if(board[i][j] == 1 || board[i][j] == -1){
int cnt = count(i,j,board);
if(cnt>=2 && cnt <= 3) board[i][j] = 1;
else board[i][j] = -1;
}else{
if(count(i,j,board) == 3) board[i][j] = 2;
}
}
}
for(int i=0;i<board.size();++i){
for(int j=0;j<board[i].size();++j){
if(board[i][j]<=0) board[i][j] = 0;
else board[i][j] = 1;
}
}
}
private:
vector<int> dx = {-1,-1,-1,0, 0, 1,1,1};
vector<int> dy = {-1, 0, 1,-1,1,-1,0,1};
};