According to the Wikipedia's article: "The Game of Life, also known simply as Life, is a cellular automaton devised by the British mathematician John Horton Conway in 1970."

Given a

*board*with*m*by*n*cells, each cell has an initial state*live*(1) or*dead*(0). Each cell interacts with its eight neighbors (horizontal, vertical, diagonal) using the following four rules (taken from the above Wikipedia article):- Any live cell with fewer than two live neighbors dies, as if caused by under-population.
- Any live cell with two or three live neighbors lives on to the next generation.
- Any live cell with more than three live neighbors dies, as if by over-population..
- Any dead cell with exactly three live neighbors becomes a live cell, as if by reproduction.

Write a function to compute the next state (after one update) of the board given its current state.

Follow up:

- Could you solve it in-place? Remember that the board needs to be updated at the same time: You cannot update some cells first and then use their updated values to update other cells.
- In this question, we represent the board using a 2D array. In principle, the board is infinite, which would cause problems when the active area encroaches the border of the array. How would you address these problems?

**[Thoughts]**

这是个模拟题。把整个过程分成两步，第一步先计算所有cell的当前值，然后再计算下一步状态。

**[Code]**

```
1: void gameOfLife(vector<vector<int>>& board) {
2: int raws = board.size();
3: if(raws == 0) return;
4: int columns = board[0].size();
5:
6: // calculate the neighbors first
7: for(int i =0; i< raws; i++) {
8: for(int j = 0; j< columns; j++) {
9: int neighbors = 0;
10: // 3X3 neighbors
11: for(int k = i-1; k<= i+1; k++) {
12: if(k<0 || k>raws-1) continue;
13: for(int l = j-1; l<=j+1; l++) {
14: if(l<0 || l> columns -1) continue;
15: if(k ==i && l == j) continue;
16: neighbors+= board[k][l]%10;
17: }
18: }
19:
20: board[i][j] = neighbors*10 + board[i][j];
21: }
22: }
23:
24: // decide current value
25: for(int i =0; i< raws; i++) {
26: for(int j = 0; j< columns; j++) {
27: int neighbors = board[i][j] /10;
28: int cur = board[i][j] %10;
29: if(cur == 1) {
30: if(neighbors < 2 || neighbors>3) {
31: board[i][j] = 0;
32: continue;
33: }
34: } else {
35: if(neighbors ==3){
36: board[i][j] = 1;
37: continue;
38: }
39: }
40: board[i][j] = cur;
41: }
42: }
43: }
```

## No comments:

Post a Comment