4ms c++ in place by storing the neighbour info in board


  • 1

    if current site state is dead/live, I use -1/1 to record the neighbour relation, and the relation info is stored in the board. Then, scan the board again and obtain the finial result.

    void gameOfLife(vector<vector<int>>& board) {
        int i, j, m=board.size(), n=board[0].size(), one;
        for(i=0; i<m; i++) for(j=0; j<n; j++){
            one=board[i][j]<=0 ? -1:1;
            board[i][j]+= i-1>=0 && board[i-1][j]>0 ? one : 0;
            board[i][j]+= i+1<m && board[i+1][j]>0 ? one : 0;
            board[i][j]+= j-1>=0 && board[i][j-1]>0 ? one : 0;
            board[i][j]+= j+1<n && board[i][j+1]>0 ? one : 0;
            if(i-1>=0){
                board[i][j]+=j-1>=0 && board[i-1][j-1]>0 ? one : 0;
                board[i][j]+=j+1<n && board[i-1][j+1]>0 ? one : 0;
            }
            if(i+1<m){
                board[i][j]+= j-1>=0 && board[i+1][j-1]>0 ? one : 0;
                board[i][j]+= j+1<n && board[i+1][j+1]>0 ? one : 0;
            }
        }
        for(i=0; i<m; i++) for(j=0; j<n; j++){
            if(board[i][j]==-3 || board[i][j]==3 || board[i][j]==4) board[i][j]=1;
            else board[i][j]=0;
        }
    }

Log in to reply
 

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