Could someone tell me why there is TLE for my BFS solution?


  • 0
    Y
    '''
    class Solution {
    public:
        void solve(vector<vector<char>>& board) {
            if(board.empty()) return;
            const int max_row(board.size()-1),max_col(board[0].size()-1);
            //check first row and last row
            for(int col=0;col<=max_col;++col){
                if(board[0][col] == 'O') bfs(board,0,col);
                if(board[max_row][col] == 'O') bfs(board,max_row,col);
            }
            //check first col and last col
            for(int row=0;row<=max_row;++row){
                if(board[row][0] == 'O') bfs(board,row,0);
                if(board[row][max_col] == 'O') bfs(board,row,max_col);
            }
            for(int row=0;row<=max_row;++row){
                for(int col=0;col<=max_col;++col){
                    board[row][col] = ( board[row][col] == 'R' ? 'O' : 'X' );
                }
            }
        }
    private:
    //this function should be called only when board[row][col]=='O'
        void bfs(vector<vector<char>>& board,
            const int row,
            const int col){
            if(board[row][col]!='O') return;
            const int max_row(board.size()-1),max_col(board[0].size()-1);
            typedef std::pair<int,int> Item;
            std::queue<Item> items;
            items.push(Item(row,col));
            while(!items.empty()){
                const Item & cur_item = items.front();
                items.pop();//remove from queue
                const int cur_row(cur_item.first),cur_col(cur_item.second);
                board[cur_row][cur_col] = 'R';
                    if(cur_row>0 && board[cur_row-1][cur_col]=='O')
                        items.push(Item(cur_row-1,cur_col));
                    if(cur_row<max_row && board[cur_row+1][cur_col]=='O')
                        items.push(Item(cur_row+1,cur_col));
                    if(cur_col>0 && board[cur_row][cur_col-1]=='O')
                        items.push(Item(cur_row,cur_col-1));
                    if(cur_col<max_col && board[cur_row][cur_col+1]=='O')
                        items.push(Item(cur_row,cur_col+1));
                    
    
             }
        }
    };
    

Log in to reply
 

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