289、生命游戏
根据 百度百科 ，生命游戏，简称为生命，是英国数学家约翰·何顿·康威在 1970 年发明的细胞自动机。
给定一个包含 m × n 个格子的面板，每一个格子都可以看成是一个细胞。每个细胞都具有一个初始状态：1 即为活细胞（live），或 0 即为死细胞（dead）。每个细胞与其八个相邻位置（水平，垂直，对角线）的细胞都遵循以下四条生存定律：
- 如果活细胞周围八个位置的活细胞数少于两个，则该位置活细胞死亡；
- 如果活细胞周围八个位置有两个或三个活细胞，则该位置活细胞仍然存活；
- 如果活细胞周围八个位置有超过三个活细胞，则该位置活细胞死亡；
- 如果死细胞周围正好有三个活细胞，则该位置死细胞复活；
根据当前状态，写一个函数来计算面板上所有细胞的下一个（一次更新后的）状态。下一个状态是通过将上述规则同时应用于当前状态下的每个细胞所形成的，其中细胞的出生和死亡是同时发生的。
示例：
输入：
[
[0,1,0],
[0,0,1],
[1,1,1],
[0,0,0]
]
输出：
[
[0,0,0],
[1,0,1],
[0,1,1],
[0,1,0]
]
进阶：
你可以使用原地算法解决本题吗？请注意，面板上所有格子需要同时被更新：你不能先更新某些格子，然后使用它们的更新后的值再更新其他格子。
本题中，我们使用二维数组来表示面板。原则上，面板是无限的，但当活细胞侵占了面板边界时会造成问题。你将如何解决这些问题？
题解
1、复制数组模拟
根据原数组将新的状态更新到新的数组，再讲新状态更新到旧的数组。
class Solution {
int[][] board0;
int row;
int col;
// 八连通增量数组
int[] di = new int[]{0,0,1,-1,1,-1,-1,1};
int[] dj = new int[]{1,-1,0,0,1,-1,1,-1};
private int getCellsNum(int i,int j) {
int count = 0;
for (int k = 0;k < 8;k++) {
int ni = i + di[k];
int nj = j + dj[k];
if (ni >= 0 && ni < row && nj >= 0 && nj < col){
count += board0[ni][nj];
}
}
return count;
}
public void gameOfLife(int[][] board) {
board0 = board;
row = board.length;
if (row == 0){
return;
}
col = board[0].length;
int[][] tmp = new int[row][col];
for (int i = 0;i < row;i++) {
for (int j = 0;j < col;j++) {
int count = getCellsNum(i,j);
if (board[i][j] == 0) {
if (count == 3){
tmp[i][j] = 1;
}
}else {
if (count == 2 || count == 3) {
tmp[i][j] = 1;
}
}
}
}
for (int i = 0;i < row;i++) {
for (int j = 0;j < col;j++) {
board[i][j] = tmp[i][j];
}
}
}
}
2、原地模拟
定义新的状态，以区分上一个状态是活还是死。
-1活 -> 死1活 -> 活2死 -> 活
最后在遍历一遍，将-1状态 和2状态 进行更新成0和1就行了。
class Solution {
int[][] board0;
int row;
int col;
// 八连通增量数组
int[] di = new int[]{0,0,1,-1,1,-1,-1,1};
int[] dj = new int[]{1,-1,0,0,1,-1,1,-1};
private int getCellsNum(int i,int j) {
int count = 0;
for (int k = 0;k < 8;k++) {
int ni = i + di[k];
int nj = j + dj[k];
if (ni >= 0 && ni < row && nj >= 0 && nj < col){
// 不是死的，也不是复活的。
count += (board0[ni][nj] == 1 || board0[ni][nj] == -1) ? 1 : 0;
}
}
return count;
}
public void gameOfLife(int[][] board) {
board0 = board;
row = board.length;
if (row == 0){
return;
}
col = board[0].length;
for (int i = 0;i < row;i++) {
for (int j = 0;j < col;j++) {
int count = getCellsNum(i,j);
if (board[i][j] == 0 && count == 3) {
// 死 -> 活
board[i][j] = 2;
}else if(board[i][j] == 1 && count != 2 && count != 3) {
// 活 -> 死
board[i][j] = -1;
}
}
}
for (int i = 0;i < row;i++) {
for (int j = 0;j < col;j++) {
if(board[i][j] == -1) {
board[i][j] = 0;
} else if (board[i][j] == 2) {
board[i][j] = 1;
}
}
}
}
}
转载请注明来源，欢迎对文章中的引用来源进行考证，欢迎指出任何有错误或不够清晰的表达。可以在下面评论区评论，也可以邮件至 1056615746@qq.com
