289. 生命游戏(中等)

Posted on In Views:

1，问题描述

289. 生命游戏

难度：中等

根据 百度百科 ， 生命游戏 ，简称为 生命 ，是英国数学家约翰·何顿·康威在 1970 年发明的细胞自动机。

给定一个包含 m × n 个格子的面板，每一个格子都可以看成是一个细胞。每个细胞都具有一个初始状态： 1 即为 活细胞 （live），或 0 即为 死细胞 （dead）。每个细胞与其八个相邻位置（水平，垂直，对角线）的细胞都遵循以下四条生存定律：

  1. 如果活细胞周围八个位置的活细胞数少于两个，则该位置活细胞死亡；
  2. 如果活细胞周围八个位置有两个或三个活细胞，则该位置活细胞仍然存活；
  3. 如果活细胞周围八个位置有超过三个活细胞，则该位置活细胞死亡；
  4. 如果死细胞周围正好有三个活细胞，则该位置死细胞复活；

下一个状态是通过将上述规则同时应用于当前状态下的每个细胞所形成的，其中细胞的出生和死亡是 同时 发生的。给你 m x n 网格面板 board 的当前状态，返回下一个状态。

给定当前 board 的状态，更新 board 到下一个状态。

注意 你不需要返回任何东西。

示例 1：

img

1
2
输入：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]]

示例 2：

img

1
2
输入：board = [[1,1],[1,0]]
输出：[[1,1],[1,1]]

提示：

  • m == board.length
  • n == board[i].length
  • 1 <= m, n <= 25
  • board[i][j] 为 0 或 1

进阶：

  • 你可以使用原地算法解决本题吗？请注意，面板上所有格子需要同时被更新：你不能先更新某些格子，然后使用它们的更新后的值再更新其他格子。
  • 本题中，我们使用二维数组来表示面板。原则上，面板是无限的，但当活细胞侵占了面板边界时会造成问题。你将如何解决这些问题？

2，初步思考

​ 模拟法解题，时间复杂度O（m*n）

​ 使用有限状态机（SVM）的原理进行处理

3，代码处理

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
package questions;


public class _289生命游戏 {

    // 使用额外的状态
    // 这种方法可以理解为有限状态机，它将状态进行存储！
    public void gameOfLife_mutiple_status(int[][] board) {
        int n = board.length, m = board[0].length;
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                board[i][j] = getStatus(board, i, j);
            }
        }

        int cur = 0;
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                cur = board[i][j];
                if (cur < 0) {
                    board[i][j] = 0;
                } else if (cur > 0) {
                    board[i][j] = 1;
                }
            }
        }
    }

    private int getStatus(int[][] board, int i, int j) {
        int n = board.length, m = board[0].length;
        int cnt = 0;
        if (i - 1 >= 0) {// 上界
            cnt += getOrigin(board[i - 1][j]);
        }
        if (i + 1 < n) {// 下界
            cnt += board[i + 1][j];
        }
        if (j - 1 >= 0) {// 左边界有
            cnt += getOrigin(board[i][j - 1]);
        }
        if (j + 1 < m) {// 右边界有
            cnt += board[i][j + 1];
        }

        if (i - 1 >= 0 && j - 1 >= 0) {// 左上
            cnt += getOrigin(board[i - 1][j - 1]);
        }
        if (i + 1 < n && j - 1 >= 0) {// 左下
            cnt += getOrigin(board[i + 1][j - 1]);
        }
        if (i - 1 >= 0 && j + 1 < m) {// 右上
            cnt += getOrigin(board[i - 1][j + 1]);
        }
        if (i + 1 < n && j + 1 < m) {// 右下
            cnt += board[i + 1][j + 1] > 0 ? 1 : 0;
        }

        if (cnt < 2 && board[i][j] > 0) {
            return -1;
        }
        if (cnt > 3 && board[i][j] > 0) {
            return -1;
        }
        if (cnt == 3 && board[i][j] == 0) {
            return 2;
        }
        return board[i][j];
    }

    private int getOrigin(int status) {
        switch (status) {
            case 1:
                return 1;
            case -1:// 1->0
                return 1;
            case 2:// 0->1
                return 0;
            default:
                return 0;
        }
    }


    // 模拟法求解
    public void gameOfLife(int[][] board) {
        int n = board.length, m = board[0].length;
        // 创建复制数组 copyBoard
        int[][] copyBoard = new int[n][m];
        for (int row = 0; row < n; row++) {
            for (int col = 0; col < m; col++) {
                copyBoard[row][col] = board[row][col];
            }
        }
        int[][] dpVertical = new int[n][m];// 竖直方向dp
        dpVertical[0] = copyBoard[0];
        for (int i = 1; i < n; i++) {
            for (int j = 0; j < m; j++) {
                dpVertical[i][j] = dpVertical[i - 1][j] + board[i][j];
            }
        }

        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                if (isValid(dpVertical, copyBoard, i, j)) {
                    board[i][j] = 1;
                } else {
                    board[i][j] = 0;
                }
            }
        }
    }

    private boolean isValid(int[][] dpVertical, int[][] board, int i, int j) {
        int count = 0;
        int n = board.length, m = board[0].length;// y坐标最大值, x坐标最大值
        int maxVidx = Math.min(i + 1, n - 1);

        if (i - 1 >= 0) {// 上界
            count += board[i - 1][j];
        }
        if (i + 1 < n) {// 下界
            count += board[i + 1][j];
        }
        if (j - 1 >= 0) {// 左边界有
            count += dpVertical[maxVidx][j - 1] - (i - 2 < 0 ? 0 : dpVertical[i - 2][j - 1]);
        }
        if (j + 1 < m) {// 右边界有
            count += dpVertical[maxVidx][j + 1] - (i - 2 < 0 ? 0 : dpVertical[i - 2][j + 1]);
        }
        if (count == 3 || (count == 2 && board[i][j] == 1)) {
            return true;
        }
        return false;
    }

    public static void main(String[] args) {
        _289生命游戏 gameOfLife = new _289生命游戏();
        int[][] board = new int[][]{
                {0, 1, 0},
                {0, 0, 1},
                {1, 1, 1},
                {0, 0, 0}};
        gameOfLife.gameOfLife_mutiple_status(board);
        for (int[] ints : board) {
            for (int anInt : ints) {
                System.out.print(anInt + " ");
            }
            System.out.println();
        }
    }
}

/**
 * 状态变化：
 * -1: 1->0
 * 0: 0->0
 * 1: 1->1
 * 2: 0->1
 */