Why is my BFS code TLE?


  • 0
    B

    Hi everyone, it seems that my BFS strategy is nothing different with others, but it always TLE. I figured for a while but can not find nothing special. Any help? Thanks!

      void solve(vector<vector<char>>& board) {
        if(board.empty() || board[0].empty()) return;
        int length=board.size(), width=board[0].size();
        
        // b[i][j]
        for(int j=0; j<width; ++j)
            search(board, 0, j);
        for(int i=1; i<length; ++i)
            search(board ,i, width-1);
        for(int j=width-2; j>=0; --j)
            search(board, length-1, j);
        for(int i=length-2; i>=0; --i)
            search(board, i, 0);
    
        for(int i=0; i<length; ++i)
            for(int j=0; j<width; ++j)
                board[i][j] = ( board[i][j]=='N')? 'O' : 'X';
        
    }
    
    void search(vector<vector<char>>& board, int i, int j){
        vector<pair<int, int>> move({{0,1}, {0,-1}, {1,0}, {-1,0}});
        
        if(board[i][j]!='O') return;
        
        queue<pair<int, int>> q;
        q.push(make_pair(i, j));
        
        while(!q.empty()){
            auto cur=q.front();
            q.pop();
            board[cur.first][cur.second]='N';
            
            for(int k=0; k<move.size(); ++k){
                pair<int, int> aj(cur.first+move[k].first, cur.second+move[k].second);
                
                if(aj.first>=0 && aj.first<board.size() && aj.second>=0 && aj.second<board[0].size() 
                               && board[aj.first][aj.second]=='O')
                               q.push(aj);
            }
        }
    }

Log in to reply
 

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