leetcode GameOfLife
z
 2019-04-09 10:36:27   
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
public class GameOfLife {
  /**
   * 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.
   * The next state is created by applying the above rules simultaneously to every cell in the current state,
   * where births and deaths occur simultaneously.
   *
   * Example:
   *
   * Input:
   * [
   *   [0,1,0],
   *   [0,0,1],
   *   [1,1,1],
   *   [0,0,0]
   * ]
   * Output:
   * [
   *   [0,0,0],
   *   [1,0,1],
   *   [0,1,1],
   *   [0,1,0]
   * ]
   *
   * 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?
   */
  public void solution(int[][] matrix){
    if (matrix == null || matrix.length == 0)
      return ;
    int index[][] = {{1,-1},{1,1},{-1,-1},{-1,1},{1,0},{-1,0},{0,1},{0,-1}};
    for (int i=0; i<matrix.length; i++){
      for (int j=0; j<matrix[0].length; j++){
        int live = 0;
        for (int[]ind: index){
          if (i+ind[0]<0 || i+ind[0]>=matrix.length || j+ind[1]<0 || j+ind[1]>=matrix[0].length) continue;
          else if (matrix[i+ind[0]][j+ind[1]] == 1 || matrix[i+ind[0]][j+ind[1]] == 2 ) live ++;
        }
        if (matrix[i][j] == 0 && live == 3) matrix[i][j] = 3;
        if (matrix[i][j] == 1 && (live<2 || live>3)) matrix[i][j] = 2;
      }
    }
    for (int i=0; i<matrix.length; i++){
      for (int j=0; j<matrix[0].length; j++) {
      matrix[i][j] = matrix[i][j] % 2;
      }
    }
  }
}