A C++ solution with a slightly different approach(with explanation)


  • 1
    P

    The problem can be broken down by looking at the entire neighborhood (including the element in consideration). Lets call this neighborhood sum of 9 elements N(i), where i is the element whose neighborhood we are currently looking at. The state of the next can be deduced by looking at N(i) as follows:

    1. if N(i) is 4, the next state will be the same as current state.This can be explained as follows. If i is 0, means there are 4 elements in the neighborhood which are 1. Hence, next state is still 0. If i is 1, three neighbors are alive(1). Hence, the state i remains 1 in the next update.

    2. If N(i) is 3, the next state is 1 for i. If i is 0, there are exactly 3 alive neighbors , so it will come back to life in the next state. If i is 1, two neighbours are alive, so it will live on to the next state.

    3. for any other case, the next state will be zero(i.e for N(i)<3 or N(i)>4).

    The code is as follows:

    class Solution {
    public:
        void gameOfLife(vector<vector<int>>& board) { vector<vector<int>> next;
            int row = board.size();
            int col = board[0].size();
            
            for(int i =0; i < row; i++)
            {
                for(int j = 0; j < col; j++)
                {
                   int sum = findSum(i,j,board, row, col);
                   // if sum of all 9 neighbours is 3, then the element is always 1
                   //if sum is 4, the current state is retained. In any other case, the state becomes 0
                   if(sum==3)
                   {
                       board[i][j] = (board[i][j] == 0 ? 2 :3);
                   }
                   else if(sum ==4)
                   {
                       board[i][j] = (board[i][j]==0 ?0 :3);
                   }
                   else board[i][j] = (board[i][j] ==0 ? 0 : 1);
                }
            }
            
            for(int i = 0; i < row; i++)
            {
                for(int j = 0; j < col; j++)
                {
                    board[i][j] = board[i][j]>>1;
                }
            }
        }
        
        int findSum(int a, int b, vector<vector<int>> matrix, int m, int n)
        {
            int count= 0;
            for(int i = a-1; i <=a+1; i++)
            {
                for(int j = b-1; j <= b+1; j++ )
                {
                    if(i>=0 && i<m && j>=0 && j<n)
                    {
                        count = count + (matrix[i][j] & 1);
                    }
                }
            }
            
            return count;
        }
    };
    

  • 1

    @pb1771 Your solution is good but actually you can make it more terse and cleaner just as follows eliminating the redundancy.

    class Solution {
    public:
        void gameOfLife(vector<vector<int>>& board) 
        {
            if(board.empty()) return ;
            int rowSize = board.size(), colSize = board[0].size();
            for(int r = 0; r < rowSize; ++r)
            {
                for(int c = 0; c < colSize; ++c)
                {
                    int count = 0;
                    for(int i = max(0, r-1); i < min(rowSize, r+2); ++i)
                        for(int j = max(0, c-1); j < min(colSize, c+2); ++j)
                            if(board[i][j]&1) count++;
                    if(count==3 || (count==4&&(board[r][c]&1))) board[r][c] |= 2;
                }
            }
            for(int r = 0; r < rowSize; ++r)
                for(int c = 0; c < colSize; ++c)
                    board[r][c] >>= 1;
        }
    };
    

  • 0
    P

    @LHearen Ah!! This is great. Thanks a lot :)


Log in to reply
 

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