According to the : "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 (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?
1.用额外空间的。先根据每个live向四面八方做贡献，给周围格子live计数++。从而先得到整个棋盘每个点的四周live计数矩阵。之后根据该矩阵和条件更新状态。
2.利用2位记录状态。00,01,10,11，低位表示当前状态，高位表示下轮状态。这样计数的时候只看board[i][j] & 1即可。就算把1改2（下轮要变0）也不会影响后续计数。
实现1：
class Solution { public void gameOfLife(int[][] board) { if (board == null || board.length == 0 || board[0].length == 0) { return; } int[][] count = new int[board.length][board[0].length]; for (int i = 0; i < board.length; i++) { for (int j = 0; j < board[0].length; j++) { count(board, i, j, count); } } for (int i = 0; i < board.length; i++) { for (int j = 0; j < board[0].length; j++) { int cnt = count[i][j]; if (board[i][j] == 0 && cnt == 3) { board[i][j] = 1; } else if (board[i][j] == 1 && (cnt < 2 || cnt > 3)) { board[i][j] = 0; } } } } private void count(int[][] board, int x, int y, int[][] count) { if (board[x][y] == 0) { return; } int[] dx = {0, 1, 0, -1, 1, 1, -1, -1}; int[] dy = {1, 0, -1, 0, 1, -1, 1, -1}; for (int i = 0; i < 8; i++) { int newX = x + dx[i]; int newY = y + dy[i]; if (isInBound(board, newX, newY)) { count[newX][newY]++; } } } private boolean isInBound(int[][] board, int x, int y) { return x >= 0 && x < board.length && y >= 0 && y < board[0].length; }}
2.实现2
class Solution { public void gameOfLife(int[][] board) { if (board == null || board.length == 0 || board[0].length == 0) { return; } for (int i = 0; i < board.length; i++) { for (int j = 0; j < board[0].length; j++) { int cnt = count(board, i, j); if (board[i][j] == 0 && cnt == 3) { board[i][j] = 2; } else if (board[i][j] == 1 && (cnt < 2 || cnt > 3)) { board[i][j] = 5; } else if (board[i][j] == 1) { board[i][j] = 3; } } } for (int i = 0; i < board.length; i++) { for (int j = 0; j < board[0].length; j++) { board[i][j] = ((board[i][j] >> 1) & 1); } } } private int count(int[][] board, int x, int y) { int[] dx = {0, 1, 0, -1, 1, 1, -1, -1}; int[] dy = {1, 0, -1, 0, 1, -1, 1, -1}; int cnt = 0; for (int i = 0; i < 8; i++) { int newX = x + dx[i]; int newY = y + dy[i]; if (isInBound(board, newX, newY) && (board[newX][newY] & 1) == 1) { cnt++; } } return cnt; } private boolean isInBound(int[][] board, int x, int y) { return x >= 0 && x < board.length && y >= 0 && y < board[0].length; }}