模拟经营手机单机游戏，生命游戏
模拟经营手机单机游戏，生命游戏你可以使用原地算法解决本题吗？下一个状态是通过将上述规则同时应用于当前状态下的每个细胞所形成的，其中细胞的出生和死亡是同时发生的。给你 m x n 网格面板 board 的当前状态，返回下一个状态。如果活细胞周围八个位置有两个或三个活细胞，则该位置活细胞仍然存活；如果活细胞周围八个位置有超过三个活细胞，则该位置活细胞死亡；如果死细胞周围正好有三个活细胞，则该位置死细胞复活；
题目：
根据 百度百科 ，生命游戏，简称为生命，是英国数学家约翰·何顿·康威在 1970 年发明的细胞自动机。
给定一个包含 m × n 个格子的面板，每一个格子都可以看成是一个细胞。每个细胞都具有一个初始状态：1 即为活细胞（live），或 0 即为死细胞（dead）。每个细胞与其八个相邻位置（水平，垂直，对角线）的细胞都遵循以下四条生存定律：
如果活细胞周围八个位置的活细胞数少于两个，则该位置活细胞死亡；
如果活细胞周围八个位置有两个或三个活细胞，则该位置活细胞仍然存活；
如果活细胞周围八个位置有超过三个活细胞，则该位置活细胞死亡；
如果死细胞周围正好有三个活细胞，则该位置死细胞复活；
下一个状态是通过将上述规则同时应用于当前状态下的每个细胞所形成的，其中细胞的出生和死亡是同时发生的。给你 m x n 网格面板 board 的当前状态，返回下一个状态。
你可以使用原地算法解决本题吗？
示例：
输入：board = [[0 1 0] [0 0 1] [1 1 1] [0 0 0]]
输出：[[0 0 0] [1 0 1] [0 1 1] [0 1 0]]
思路：
修改单个元素的状态时，需要保留修改前的状态信息，这样后续元素依赖该元素时，才能正确计算活细胞的个数。
目前矩阵中的状态有两种：0，1，为了保留修改前的状态，引入复合状态：从0修改到1 记为2；从1修改成0，记为-1。这样：
2既能表示当前细胞状态是1，也能表示修改前的状态是0；
-1既能表示当前细胞状态是0，也能表示修改前的状态是1。
代码：
class Solution {
public:
//统计元素周围的活细胞个数
int count(vector<vector<int>>& board const int& m const int& n const int& i const int& j)
{
int result = 0;
int dir[] = {-1 0 1};
for(int row_dir_idx=0; row_dir_idx<3; row_dir_idx )
{
for(int col_dir_idx=0; col_dir_idx<3; col_dir_idx )
{
if(row_dir_idx==1 && col_dir_idx==1)
continue;
int new_i = i dir[row_dir_idx];
int new_j = j dir[col_dir_idx];
if( new_i>=0 && new_i<m && new_j>=0 && new_j<n)
{
if(board[new_i][new_j] == 1 || board[new_i][new_j] == -1)
result ;
}
}
}
return result;
}
void gameOfLife(vector<vector<int>>& board) {
int m = board.size();
int n = board[0].size();
//遍历矩阵，根据规则设置新的状态
for(int i=0; i<m; i )
{
for(int j=0; j<n; j )
{
int k = count(board m n i j);
if(k<2 && board[i][j]==1)
board[i][j] = -1;
else if(k==3 && board[i][j]==0)
board[i][j] = 2;
else if(k>3 && board[i][j]==1)
board[i][j] = -1;
}
}
//修复2 -1
for(int i=0; i<m; i )
{
for(int j=0; j<n; j )
{
if(board[i][j]==-1)
board[i][j]=0;
else if(board[i][j]==2)
board[i][j]=1;
}
}
}
};
