Why my BFS got an TLE on big dataset


  • 1
    T

    Here is my BFS, nothing special, but got an TLE on the big input. I saw other people got passed and mine DFS as well. Do I make any typo? Thanks for pointing it out!!!

    void bfs(vector<vector<char>>& grid, int i, int j)
    {
        queue<pair<int, int>> qe;
        qe.push({i, j});
        while(!qe.empty())
        {
            pair<int, int> pt = qe.front();
            qe.pop();
            int row = pt.first, col = pt.second;
            grid[row][col] = 'x';
            if(row > 0 && grid[row  - 1][col] == '1')
                qe.push({row - 1, col});
            if(col > 0 && grid[row][col - 1] == '1')
                qe.push({row, col - 1});
            if(row < (grid.size() - 1) && grid[row + 1][col] == '1')
                qe.push({row + 1, col});
            if(col < (grid[0].size() - 1) && grid[row][col + 1] == '1')
                qe.push({row, col + 1});
        }
    }
    int numIslands(vector<vector<char>>& grid) {
        int res = 0;
        
        for(int i = 0; i < grid.size(); ++i)
        {
            for(int j = 0; j < grid[0].size(); ++j)
            {
                if(grid[i][j] == '1')
                {
                    bfs(grid, i, j);
                    res++;
                }
            }
        }
        return res;
        
    }

  • 2
    L

    You should mark a point as x before you push it into the queue. Otherwise it would be pushed again when its neighbor is visited.


  • 0
    T

    I don't think so. When its neighbor is visited, this point is 'x' already because it has been marked as 'x' before pushing its neighbor.


  • 0
    L
    if(row > 0 && grid[row  - 1][col] == '1')
                qe.push({row - 1, col});
            if(col > 0 && grid[row][col - 1] == '1')
                qe.push({row, col - 1});
            if(row < (grid.size() - 1) && grid[row + 1][col] == '1')
                qe.push({row + 1, col});
            if(col < (grid[0].size() - 1) && grid[row][col + 1] == '1')
                qe.push({row, col + 1});
    

    I used to have similar code as yours.
    before you push these four points, mark them as x.
    Delete the line grid[row][col] = 'x';
    Your code will pass.


  • 0
    L

    I had similar question just like yours.

    What you should NOT do is to mark the grid when popping.

    Instead, should mark the grid when visiting, then push it. So basically in each if statement, add the

    grid[row][col] = 'x';


Log in to reply
 

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