289_生命游戏

难度：中等

题目

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

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

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

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

示例

示例一：

img

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

示例二：

img

输入：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

解题

在解题过程中要注意不能修改原值，否则会对下一次的结果产生影响。这里通过复制 board 来解决这个问题。

1
2
3
4
5
6
7
int m = board.length, n = board[0].length;
int[][] copy = new int[m][n];
for (int i = 0; i < m; i++) {
  for (int j = 0; j < n; j++) {
    copy[i][j] = board[i][j];
  }
}

对于每个节点，都要遍历周围邻居，只处理符合条件的邻居，数出邻居数

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
int[] neighbors = {-1,0,1};
int liveNeighbors = 0;
for (int k = 0; k < 3; k++) {
  for (int l = 0; l < 3; l++) {
    // 排除自身
    if (!(neighbors[k]==0 && neighbors[l]==0)){
      int r = i+neighbors[k];
      int c = j+neighbors[l];
      // 只处理符合条件的
      if (r<m&&r>=0 && c<n&&c>=0 &&copy[r][c]==1){
        liveNeighbors+=1;
      }
    }
  }
}

最后根据规则修改原值

1
2
3
4
5
6
7
8
// 规则 1 或 3
if (copy[i][j]==1&&(liveNeighbors<2||liveNeighbors>3)){
  board[i][j] = 0;
}
// 规则 4
if (copy[i][j] == 0 && liveNeighbors==3){
  board[i][j] = 1;
}

结合起来

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
public void gameOfLife(int[][] board){
  int[] neighbors = {-1,0,1};
  int m = board.length, n = board[0].length;
  int[][] copy = new int[m][n];
  for (int i = 0; i < m; i++) {
    for (int j = 0; j < n; j++) {
      copy[i][j] = board[i][j];
    }
  }

  for (int i = 0; i < m; i++) {
    for (int j = 0; j < n; j++) {
      int liveNeighbors = 0;
      for (int k = 0; k < 3; k++) {
        for (int l = 0; l < 3; l++) {
          if (!(neighbors[k]==0 && neighbors[l]==0)){
            int r = i+neighbors[k];
            int c = j+neighbors[l];
            if (r<m&&r>=0 && c<n&&c>=0 &&copy[r][c]==1){
              liveNeighbors+=1;
            }
          }
        }
      }
      // 规则 1 或 3
      if (copy[i][j]==1&&(liveNeighbors<2||liveNeighbors>3)){
        board[i][j] = 0;
      }
      // 规则 4
      if (copy[i][j] == 0 && liveNeighbors==3){
        board[i][j] = 1;
      }
    }
  }
}