Game of Life

Problem

Game of Life

Intuition

1. the easiest way is to copy the board and count the cells arount some one.
2. However, there is a better way that we don’t need the copied board and we can finish the task in place. We can label some cells whose states are changed with some speical number. Lastly, we can recover the special number into the right numbers.

Code

class Solution {
    private final int[] dx = {-1, -1, -1, 0, 0, 1, 1, 1};
    private final int[] dy = {-1, 0, 1, -1, 1, -1, 0, 1};
    public void gameOfLife(int[][] board) {
        for(int i = 0; i < board.length; i ++){
            for(int j = 0; j < board[0].length; j ++){
                int cnt = 0;
                for(int k = 0; k < dx.length; k ++){
                    int x = i + dx[k], y = j + dy[k];
                    if(x >= 0 && y >= 0 && x < board.length && y < board[0].length){
                        if(board[x][y] <= 1){
                            cnt += board[x][y];
                        } else if(board[x][y] >= 3){
                            cnt ++;
                        }
                    }
                }
                if(board[i][j] == 0 && cnt == 3){
                    board[i][j] = 2;
                } else if(board[i][j] == 1){
                    if(cnt <= 1 || cnt > 3){
                        board[i][j] = 3;
                    } else {
                        board[i][j] = 4;
                    }
                }
            }
        }
        for(int i = 0; i < board.length; i ++){
            for(int j = 0; j < board[0].length; j ++){
                if(board[i][j] == 2 || board[i][j] == 4){
                    board[i][j] = 1;
                } else if(board[i][j] == 3){
                    board[i][j] = 0;
                }
            }
        }
    }
}