289. Game of Life

清疚 2022-02-04 03:13 200阅读 0赞

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?

PS：从本题开始不按顺序刷题了。开始按照分类刷题，会给每篇文章额外添加一个分类。

题目是非常简单的题目，使用一个额外的数组记录每个细胞的活着的邻居数量就行；只是题目要求不要用额外的空间，且原地更改，就会稍有困难。

其实换个思路就会很好解决。原数组的1或0只是区分细胞是否活着而已，不妨重新定义是否存活，当board\[i\]\[j\]>0表示存活，否则表示死亡。然后在不冲突的情况下，用board\[i\]\[j\]的绝对值表示活着的邻居数量；此时就很好的满足题目不使用额外空间的要求了。只是有一个特例，当一个活着的细胞拥有0个活着的邻居时，按前面两层定义无法给出一个数，但根据判断是否存活的4个要素，可以给此时board\[i\]\[j\]定义为4，即最后该细胞都会死亡，与第二层定义相同，也同时满足了第一层定义。

完整代码如下：

public void gameOfLife(int[][] board) {
            int m = board.length;
            if(m == 0)
                return;
            int n = board[0].length;
            int[] dx = new int[]{-1, 0, 1, -1, 1, -1, 0, 1};
            int[] dy = new int[]{-1, -1, -1, 0, 0, 1, 1, 1};
            int isAlive, neighbors, x, y;
            for(int i = 0; i < m; ++i) {
                for(int j = 0; j < n; ++j) {
                    isAlive = board[i][j] == 0 ? -1 : 1;
                    neighbors = 0;
                    for(int k = 0; k < 8; ++k) {
                        x = i + dx[k];
                        y = j + dy[k];
                        if(0 <= x && x < m && 0 <= y && y < n && board[x][y] > 0)
                            ++neighbors;
                    }
                    if(neighbors != 0)
                        board[i][j] = isAlive * neighbors;
                    else if(isAlive == 1)
                        board[i][j] = 4;
                    else
                        ;
                }
            }
            for(int i = 0; i < m; ++i) {
                for(int j = 0; j < n; ++j) {
                    if(board[i][j] == 2 || board[i][j] == 3 || board[i][j] == -3)
                        board[i][j] = 1;
                    else
                        board[i][j] = 0;
                }
            }
        }