C++ Implementation with full comments and explanation


  • 2
    A
    class Solution {
    public:
        void gameOfLife(vector<vector<int>>& board) {
            int m = board.size(); // number of rows
            int n = board[0].size(); // number of columns
            // go through each cell and decide their condition, using (i,j) as index
            for (int i=0;i<m;i++){ 
                for (int j=0;j<n;j++){
                    int count = 0; // define a variable to store the number of board[i][j]'s currently living neighbors
                    // go through all 8 neighbors of board[i][j], using (k,l) as index
                    for (int k=(((i-1)>=0)?(i-1):0);k<=(((i+1)<=(m-1))?(i+1):(m-1));k++){
                        for (int l=(((j-1)>=0)?(j-1):0);l<=(((j+1)<=(n-1))?(j+1):(n-1));l++){
                            // if (k<0 || l<0) continue; // skip the neighbors that lie outside the board
                            if (k==i && l==j) continue; // skip board[i][j] itself
                            if ((board[k][l]&1) == 1) {
                                count += 1;
                            }
                        }
                    }
                    // The living condition of board[i][j], is also stored board[i][j], but in the 2nd bit from the right end
                    if (board[i][j] == 1){ // if current state is alive
                        // if living neighbors less than 2 or bigger than 3, then dies, but we don't need to modify board[i][j], just make the 2nd last bit stays as "0"
                        if (count == 2 || count ==3) {board[i][j] = board[i][j]|2;} // if 2 or 3 living neighbors, then lives, set the 2nd last bit to "1"
                    }
                    else if (board[i][j] == 0) { // if current state is dead
                        if (count == 3) {board[i][j] = board[i][j]|2;} // if living neighbors exactly 3, then reproduction makes the current cell live, set the 2nd last bit to "1"
                        // In other situations, board[i][j] would stay dead, and for the same reason as above, we don't do anything in this case
                    }
            }
        }
        for (int i=0;i<m;i++){
            for (int j=0;j<n;j++){
                board[i][j] = board[i][j] >> 1; // shift board[i][j] right, so that living condition info (originally the 2nd last bit) is now exposed as the last bit
            }
        }
    }
    };

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.