Personal Blog
0%

leetcode第289之生命游戏

发表于 更新于 分类于

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

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

如果活细胞周围八个位置的活细胞数少于两个，则该位置活细胞死亡；
如果活细胞周围八个位置有两个或三个活细胞，则该位置活细胞仍然存活；
如果活细胞周围八个位置有超过三个活细胞，则该位置活细胞死亡；
如果死细胞周围正好有三个活细胞，则该位置死细胞复活；
根据当前状态，写一个函数来计算面板上细胞的下一个（一次更新后的）状态。下一个状态是通过将上述规则同时应用于当前状态下的每个细胞所形成的，其中细胞的出生和死亡是同时发生的。

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
/**
 * leetcode 生命游戏
 * @param {number[][]} board
 * @return {void} Do not return anything, modify board in-place instead.
 */
var gameOfLife = function(board) {
    //额外空间法
  let tempArr = [];
  for (let i = 0; i < board.length; i++) {
    let [...arr] = board[i];
    tempArr.push(arr);
  }
  const flag = (point, data, flag) => {
    let count = 0;
    let top = 0,
      bottom = data.length - 1;
    //上下左右四个边界
    //八个点 循环三层
    if (top < point.x) {
      //说明当前节点的上一层节点存在至少一个节点
      for (let i = point.y - 1; i <= point.y + 1; i++) {
        if (data[point.x - 1][i] == flag) {
          ++count;
        }
      }
    }
    for (let i = point.y - 1; i <= point.y + 1; i++) {
      if (data[point.x][i] == flag && i != point.y) {
        ++count;
      }
    }
    if (bottom > point.x) {
      for (let i = point.y - 1; i <= point.y + 1; i++) {
        if (data[point.x + 1][i] == flag) {
          ++count;
        }
      }
    }
    return count;
  };
  for (let x = 0; x < board.length; x++) {
    for (let y = 0; y < board[0].length; y++) {
      const point = {
        x,
        y
      };
      const count = flag(point, board, 1);
      if (count < 2 && board[x][y] == 1) {
        tempArr[x][y] = 0;
      } else if ((count == 2 || count == 3) && board[x][y] == 1) {
        tempArr[x][y] = 1;
      } else if (count > 3 && board[x][y] == 1) {
        tempArr[x][y] = 0;
      } else if (count == 3 && board[x][y] == 0) {
        tempArr[x][y] = 1;
      }
    }
  }

  return Object.assign(board, tempArr);
};

// console.log("gameOfLife([\r\n    [0,1,0],\r\n    [0,0,1],\r\n    [1,1,1],\r\n    [0,0,0]\r\n  ]):", gameOfLife([
//     [0,1,0],
//     [0,0,1],
//     [1,1,1],
//     [0,0,0]
//   ]));
// gameOfLife([
//     [0,1,0],
//     [0,0,1],
//     [1,1,1],
//     [0,0,0]
//   ]);

var _gameOfLife = function(board) {
    //原地算法
  const flag = (point, data, flag) => {
    let count = 0;
    let top = 0,
      bottom = data.length - 1;
    
    //上下左右四个边界
    //八个点 循环三层
    if (top < point.x) {
      //说明当前节点的上一层节点存在至少一个节点
      for (let i = point.y - 1; i <= point.y + 1; i++) {
        if (data[point.x - 1][i] == flag[0]||data[point.x - 1][i] == flag[1]) {
          ++count;
        }
      }
    }
    for (let i = point.y - 1; i <= point.y + 1; i++) {
      if ((data[point.x ][i] == flag[0]||data[point.x ][i] == flag[1]) && i != point.y) {
        ++count;
      }
    }
    if (bottom > point.x) {
      for (let i = point.y - 1; i <= point.y + 1; i++) {
        if (data[point.x +1][i] == flag[0]||data[point.x +1][i] == flag[1]) {
          ++count;
        }
      }
    }
    return count;
  };
  for (let x = 0; x < board.length; x++) {
    for (let y = 0; y < board[0].length; y++) {
      const point = {
        x,
        y
      };
      //alive -> dead -2
      //dead -> alive 2
      const count = flag(point, board, [1,-2]);
      if (count < 2 && board[x][y] == 1) {
        board[x][y] = -2;
      } else if ((count == 2 || count == 3) && board[x][y] == 1) {
        board[x][y] = 1;
      } else if (count > 3 && board[x][y] == 1) {
        board[x][y] = -2;
      } else if (count == 3 && board[x][y] == 0) {
        board[x][y] = 2;
      }
    }
  }
  for (let x = 0; x < board.length; x++) {
    for (let y = 0; y < board[0].length; y++) {
      if (board[x][y] == -2) {
        board[x][y]=0;
      } else if(board[x][y]==2){
        board[x][y]=1;
      }
    }
  }
  return board;
};

console.log("\r\n_gameOfLife([\r\n    [0,1,0],\r\n    [0,0,1],\r\n    [1,1,1],\r\n    [0,0,0]\r\n  ]):", 
_gameOfLife([
    [0,1,0],[0,0,1],[1,1,1],[0,0,0]
  ]));

_gameOfLife([
    [0,1,0],[0,0,1],[1,1,1],[0,0,0]
  ])