LintCode 1301 · Game of Life.java

	// T O(mn) S O(1), 2 passes - Simulation
	public class Solution {
	/**
	* @param board: the given board
	* @return: nothing
	*/
	public void gameOfLife(int[][] board) {
	// Write your code here
	if (board == null || board.length == 0 || board[0] == null || board[0].length == 0) {
	return ;
	}
	// 1st pass:
	// Live to die : if (cnt < 2) setTo 2/TO_DIE（依然>=1）
	// Dead to live: if (cnt == 3) setTo -1/REBORN（依然<=0）
	int n = board.length, m = board[0].length;
	for (int i = 0; i < n; i++) {
	for (int j = 0; j < m; j++) {
	int state = board[i][j];
	int livingCount = getLivingNeighborsCount(board, i, j, n, m);
	if (state == 1) {
	if (livingCount < 2 || livingCount > 3) {
	board[i][j] = TO_DIE;
	}
	} else {
	if (livingCount == 3) {
	board[i][j] = REBORN;
	}
	}
	}
	}
	// 2nd pass:
	// turn 2/ TO_DIE into 0
	// turn -1/ REBORN into 1
	for (int i = 0; i < n; i++) {
	for (int j = 0; j < m; j++) {
	int state = board[i][j];
	if (state == TO_DIE) {
	board[i][j] = 0;
	} else if (state == REBORN) {
	board[i][j] = 1;
	}
	}
	}
	}
	private final int TO_DIE = 2;
	private final int REBORN = -1;
	private final int[] dx = new int[]{-1, -1, -1, 0, 0, 1, 1, 1};
	private final int[] dy = new int[]{-1, 0, 1, -1, 1, -1, 0, 1};
	private int getLivingNeighborsCount(int[][] board, int i, int j, int n, int m) {
	int counter = 0;
	for (int k = 0; k < 8; k++) {
	int x = dx[k] + i;
	int y = dy[k] + j;
	if (!isValid(x, y, n, m)) {
	continue;
	}
	if (board[x][y] >= 1) {
	counter++;
	}
	}
	return counter;
	}
	private boolean isValid(int i, int j, int n, int m) {
	return i >= 0 && i < n && j >= 0 && j < m;
	}
	}

view raw LintCode 1301 · Game of Life.java hosted with ❤ by GitHub