C++ inplace solution


  • 0
    A
    class Solution {
    public:
        enum Status{
            Dead = 0,
            Live = 1,
            L2D = 2, //live to dead
            D2L = 3  //dead to live
        };
    public:
        void gameOfLife(vector<vector<int>>& board) {
            m = board.size();
            if(m<0) return;
            n = board[0].size();
            if(n<0) return;
            
            for(int i=0; i<m; i++){
                for(int j=0; j<n; j++){
                    update_transition(board, i, j);
                }
            }
            
             for(int i=0; i<m; i++){
                for(int j=0; j<n; j++){
                    update_final(board, i, j);
                }
            }       
        }
        
    private:
        int was_live(vector<vector<int>>& board, int i, int j){
            //the board is infinite,
            //i = i<0? m-1 : i>m? 0: i;
            //j = j<0? n-1 : j>n? 0: j;
            if(i<0||i>=m||j<0||j>=n) return 0;
            if(board[i][j]==Status::Live || board[i][j] == Status::L2D) return 1;
            return 0;
        }
        
        void update_transition(vector<vector<int>>& board, int i, int j){
            int cnt = 0;
            int move[16] = {0,1, 1,0, 0,-1, -1,0, -1,-1, 1,1, -1,1, 1,-1};
            for(int k=0; k<16; k+=2){
                cnt += was_live(board, i+move[k], j+move[k+1]);
            }
            
            if(board[i][j]) {
                if(cnt<2 || cnt>3) board[i][j] = Status::L2D;
            }else{
                if(cnt == 3) board[i][j] = Status::D2L;
            }
        }
        
        void update_final(vector<vector<int>>& board, int i, int j){
            switch(board[i][j]){
                case Status::L2D: board[i][j]=Status::Dead; break;
                case Status::D2L: board[i][j]=Status::Live; break;
                default: break;
            }
        }
        
    private:
        int m;
        int n;
    };

Log in to reply
 

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