289 Game of Life

289. Game of Life

1. Question

According to the [Wikipedia's article]([[https://en.wikipedia.org/wiki/Conway's_Game_of_Life](https://en.wikipedia.org/wiki/Conway's_Game_of_Life)](https://en.wikipedia.org/wiki/Conway's_Game_of_Life]%28https://en.wikipedia.org/wiki/Conway's_Game_of_Life%29)\): "The Game of Life, also known simply as Life, is a cellular automaton devised by the British mathematician John Horton Conway in 1970."

Given aboard 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):

1. Any live cell with fewer than two live neighbors dies, as if caused by under-population.

2. Any live cell with two or three live neighbors lives on to the next generation.

3. Any live cell with more than three live neighbors dies, as if by over-population..

4. 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:

1. 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.

2. 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?

2. Implementation

思路: 分别用0，1，2，3代表4种状态转移

0: dead -> dead

1: live -> live

2: live -> dead

3: dead -> live

最后在第二次遍历矩阵时，对每个矩阵的数模2就可以得到最后状态

class Solution {
    public void gameOfLife(int[][] board) {
        if (board == null || board.length == 0) {
            return;
        }

        int m = board.length, n = board[0].length;
        int[][] directions = {{-1, -1}, {-1, 0}, {-1, 1}, {0, -1}, {0, 1}, {1, -1}, {1, 0}, {1, 1}};

        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                int lives = 0;

                for (int[] direction : directions) {
                    int nextRow = i + direction[0];
                    int nextCol = j + direction[1];

                    if (isValid(nextRow, nextCol, board)) {
                        ++lives;
                    }
                }

                if (board[i][j] == 1 && (lives < 2 || lives > 3)) {
                    board[i][j] = 2;
                }
                else if (board[i][j] == 0 && lives == 3) {
                    board[i][j] = 3;
                }
            }
        }

        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                board[i][j] %= 2;
            }
        }
    }

    public boolean isValid(int row, int col, int[][] board) {
        return row >= 0 && row < board.length && col >= 0 && col < board[0].length && (board[row][col] == 1 || board[row][col] == 2);
    }
}

（2） Follow up, 矩阵很大时怎么办？

https://leetcode.com/problems/game-of-life/discuss/73217/Infinite-board-solution

用MapReduce的做法: https://segmentfault.com/a/1190000003819277

3. Time & Space Complexity

时间复杂度O(mn), 空间复杂度O(mn)