289. Game of Life
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.
方法
实际上这是一道比较简单的题，但是读懂题意很重要，一开始觉得超难，想着，我的天呐，难道每改一个Cell的状态，其余的Cell状态都要改吗，实际上认真读题发现并不需要，其余的Cell只要保持原状态就可以了，那就简单了。
本人用了一个比较简单的技巧，因为每个Cell只有两种状态1和0，那么0-->00,1-->01，第0位表示当前状态，第一位表示下一个状态，例如一个Cell，周围若live 2个或3个Cell,那么它的下一个状态就为1,即01-->11 <=> 1-->3。
public class Solution {
public void gameOfLife(int[][] board) {
if(board == null || board.length <=0 ){
return;
}
int m = board.length;
int n = board[0].length;
int live = 0;
for(int i = 0; i < m; i++){
for(int j = 0; j < n; j++){
live = find(board,m,n,i,j);
if(board[i][j] == 1 && (live == 2 || live == 3)){
board[i][j] = 3;
}
if(board[i][j] == 0 && live == 3){
board[i][j] = 2;
}
}
}
for(int i = 0; i < m; i++){
for(int j = 0; j < n; j++){
board[i][j] = board[i][j] >> 1;
}
}
}
public int find(int[][] board, int m, int n, int i, int j){
int live = 0;
for(int x = Math.max(i-1,0); x <= Math.min(i+1,m-1); x++){
for(int y = Math.max(j-1,0); y <= Math.min(j+1,n-1); y++){
live = live + (board[x][y] & 1);
}
}
live = live - (board[i][j] & 1);
return live;
}
}