There might be something wrong with the OJ


  • 0

    The solution below will run into RE(Runtime Error) but the second version of it will not, which just remove the border checking, but actually in the first version the border checking is also automatically removed by the first statement:

    if(board[r][c] != big_O) return ; //in case of re-checking backwards;

    function fillup will be being invoked in the border of the board, the big_O will be replaced by mask directly, which means the function fillup will be terminated immediately when coming to the edge of the board!

    the only difference is not a true difference then

    <font color="#ff0000">So what's the real problem causing the RuntimeError? Something wrong with the OJ again?</font>


    class Solution {
    private:
        const char mask = 'a';
        const char big_O = 'O';
        const char big_X = 'X';
        int rowSize, colSize;
        void fillup(vector<vector<char>>& board, int r, int c)
        {
            if(board[r][c] != big_O) return ;  //in case of re-checking backwards;
            board[r][c] = mask;
            if(r-1>-1 && board[r-1][c]==big_O) fillup(board, r-1, c);
            if(c-1>-1 && board[r][c-1]==big_O) fillup(board, r, c-1);
            if(r+1<rowSize && board[r+1][c]==big_O) fillup(board, r+1, c);
            if(c+1<colSize && board[r][c+1]==big_O) fillup(board, r, c+1);
        }
        
    public:
        void solve(vector<vector<char>>& board) {
            rowSize = board.size();
            if(!rowSize) return ;
            colSize = board[0].size();
            for(int r = 0; r < rowSize; r++)
                for(int c = 0; c < colSize; c++)
                    if((c==0 || c==colSize-1 || r==0 || r==rowSize-1) && board[r][c]==big_O) fillup(board, r, c);
            for(int r = 0; r < rowSize; r++)
                for(int c = 0; c < colSize; c++)
                {
                    if(board[r][c] == mask) board[r][c] = big_O;
                    else board[r][c] = big_X;
                }
        }
    };
    

    The valid solution is enclosed below only the border shrinks inwards:


    class Solution {
    private:
        const char mask = 'a';
        const char big_O = 'O';
        const char big_X = 'X';
        int rowSize, colSize;
        void fillup(vector<vector<char>>& board, int r, int c)
        {
            if(board[r][c] != big_O) return ;  //in case of re-checking backwards;
            board[r][c] = mask;
            if(r-1>0 && board[r-1][c]==big_O) fillup(board, r-1, c);
            if(c-1>0 && board[r][c-1]==big_O) fillup(board, r, c-1);
            if(r+2<rowSize && board[r+1][c]==big_O) fillup(board, r+1, c);
            if(c+2<colSize && board[r][c+1]==big_O) fillup(board, r, c+1);
        }
        
    public:
        //AC - 12ms - best-submission
        void solve(vector<vector<char>>& board) {
            rowSize = board.size();
            if(!rowSize) return ;
            colSize = board[0].size();
            for(int r = 0; r < rowSize; r++)
                for(int c = 0; c < colSize; c++)
                    if((c==0 || c==colSize-1 || r==0 || r==rowSize-1) && board[r][c]==big_O) fillup(board, r, c);
            for(int r = 0; r < rowSize; r++)
                for(int c = 0; c < colSize; c++)
                {
                    if(board[r][c] == mask) board[r][c] = big_O;
                    else board[r][c] = big_X;
                }
        }
    };

  • 0

    An iterative and more robust version is also provided here as follows:


    class Solution {
    private:
             const char mask = 'a';
    public:
        void solve(vector<vector<char>>& board) 
        {
            int rowSize = board.size();
            if(!rowSize) return ; 
            int colSize = board[0].size();
            stack<int> rows, cols;
            for(int r = 0; r < rowSize; r++)
            for(int c = 0; c < colSize; c++)
            if((r==0 || r==rowSize-1 || c==0 || c==colSize-1) && board[r][c] == 'O') rows.push(r), cols.push(c);
            while(!rows.empty())
            {
                int r=rows.top(), c=cols.top();
                board[r][c] = mask;
                rows.pop(), cols.pop();
                if(r-1>-1 && board[r-1][c]=='O') rows.push(r-1), cols.push(c);
                if(r+1<rowSize && board[r+1][c]=='O') rows.push(r+1), cols.push(c);
                if(c-1>-1 && board[r][c-1]=='O') rows.push(r), cols.push(c-1);
                if(c+1<colSize && board[r][c+1]=='O') rows.push(r), cols.push(c+1);
            }
            for(int r = 0; r < rowSize; r++)
                for(int c = 0; c < colSize; c++)
                    if(board[r][c] == mask) board[r][c] = 'O';
                    else board[r][c] = 'X';
        }
    };

Log in to reply
 

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