leetcode-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]
]

解决思路

首先我们分析题目，题目很好理解都能看懂不说了。思路就是对于每个细胞我们进行八个方向的遍历，然后对于细胞为活的我们进行计数。将计数结果对于要求进行判断，并进行赋值。注意的是，题目要求的是所有细胞同时更新，所以我们不能将上面更新的数组作为未更新的数组的判断。我们要先复制一个原数组用来做全局的判断。

具体实现代码如下

class Solution {
  //定义方向数组
    private int[] x = {1, 0, -1, 1, 0, -1, 1, -1};
    private int[] y = {1, 1, 1, -1, -1, -1, 0, 0};

    public void gameOfLife(int[][] board) {
//复制数组进行额外保存，方便同时进行更新
        int[][] flag = new int[board.length][board[0].length];
        for(int i = 0; i < board.length; i++){
            for(int j  = 0; j < board[0].length; j++){
                flag[i][j] = board[i][j];
            }
        }
//对数组里面的每一个细胞进行判断
        for (int i = 0; i < board.length; i++) {
            for (int j = 0; j < board[0].length; j++) {
                if (board[i][j] == 1) {
                    int sum = change(i, j, flag);
                    if(sum > 3 || sum < 2){
                        board[i][j] = 0;
                    }
                } else if(board[i][j] == 0){
                    int sum = change(i, j, flag);
                    if(sum == 3){
                        board[i][j] = 1;
                    }
                }
            }
        }
    }
//参数坐标和原数组，对八个方向进行判断
    private int change(int m, int n, int[][] flag) {
        int num = 0;
        for (int i = 0; i < 8; i++) {
            int dx = m + x[i];
            int dy = n + y[i];
            if (dx < flag.length && dx >= 0
                    && dy < flag[0].length
                    && dy >= 0){
                if(flag[dx][dy] == 1){
                    num++;
                }
            }
        }
        return num;
    }
}