BFS flood-fill takes too long when updating conditions outside the if conditions

Question

I am solving this question on GeeksForGeeks, Flood fill Algorithm:

An image is represented by a 2-D array of integers, each integer representing the pixel value of the image.

Given a coordinate (sr, sc) representing the starting pixel (row and column) of the flood fill, and a pixel value newColor, "flood fill" the image.

To perform a "flood fill", consider the starting pixel, plus any pixels connected 4-directionally to the starting pixel of the same color as the starting pixel, plus any pixels connected 4-directionally to those pixels (also with the same color as the starting pixel), and so on. Replace the color of all of the aforementioned pixels with the newColor.

I used a BFS algorithm. I am getting an Time Limit Exceeded error when I update conditions outside the if conditions in the while loop, like so:

void bfs( vector<vector<int>>& vis , vector<vector<int>>& image , int sr ,int sc, int newcolor, int ol)
    {
        pair<int,int> p = {sr,sc};
        queue<pair<int,int>> q;
        q.push(p);
        vis[sr][sc] = 1; 
        image[sr][sc] = newcolor;
        while(!q.empty())
        {
            int x = q.front().first;
            int y = q.front().second;
            vis[x][y] = 1; 
            image[x][y] = newcolor;
            q.pop();
            if(  (x-1>=0) && (image[x-1][y] == ol && vis[x-1][y] ==0))
            {  
                q.push({x-1,y});
            }
            if(  (y+1< image[0].size()) && image[x][y+1] == ol && vis[x][y+1] ==0 )
            {  
                q.push({x,y+1});
            }
            if( (x+1< image.size()) && image[x+1][y] == ol && vis[x+1][y] ==0 )
            {  
                q.push({x+1,y});
            }
            if( (y-1 >= 0) && image[x][y-1] == ol && vis[x][y-1] ==0 )
            {  
                q.push({x,y-1});
            }
        }
    }

    vector<vector<int>> floodFill(vector<vector<int>>& image, int sr, int sc, int newColor) {
       {
            vector<int> temp(image[0].size(),0);
            vector<vector<int>>vis(image.size(), temp);
            int ol = image[sr][sc];
            if(ol == newColor)
            {
                return image;
            }
            bfs(vis , image , sr, sc ,newColor , ol);
                   
            return image;
       }

But when I updated the visited array and image inside the if condition before pushing to the queue. It was working fine

    void bfs( vector<vector<int>>& vis , vector<vector<int>>& image , int sr ,int sc, int newcolor, int ol)
    {
        pair<int,int> p = {sr,sc};
        queue<pair<int,int>> q;
        q.push(p);
        vis[sr][sc] = 1; 
        image[sr][sc] = newcolor;
        while(!q.empty())
        {
            int x = q.front().first;
            int y = q.front().second;
            
            q.pop();
            if(  (x-1>=0) && (image[x-1][y] == ol && vis[x-1][y] ==0))
            {  
                vis[x-1][y] = 1; 
                image[x-1][y] = newcolor;
                q.push({x-1,y});
            }
            if(  (y+1< image[0].size()) && image[x][y+1] == ol && vis[x][y+1] ==0 )
            {   
                vis[x][y+1] = 1; 
                image[x][y+1] = newcolor;
                q.push({x,y+1});
            }
            if( (x+1< image.size()) && image[x+1][y] == ol && vis[x+1][y] ==0 )
            {   
                vis[x+1][y] = 1; 
                image[x+1][y] = newcolor;
                q.push({x+1,y});
            }
            if( (y-1 >= 0) && image[x][y-1] == ol && vis[x][y-1] ==0 )
            {   
                vis[x][y-1] = 1; 
                image[x][y-1] = newcolor;
                q.push({x,y-1});
            }
        }
    }

    vector<vector<int>> floodFill(vector<vector<int>>& image, int sr, int sc, int newColor) {
       {
            vector<int> temp(image[0].size(),0);
            vector<vector<int>>vis(image.size(), temp);
            int ol = image[sr][sc];
            if(ol == newColor)
            {
                return image;
            }
            bfs(vis , image , sr, sc ,newColor , ol);
                   
            return image;
       }
    }
};

What is the reason, both should do the same work right?

Answer 1

The second version ensures that a point will only occur once in the queue, while the first version of the code allows the same point to occur multiple times in the queue.

This means the queue can get longer than in the first version, and more iterations are needed of the loop.

Note that also the second version can be improved: as bfs is only called when the new color is different from the color of the starting point, you don't actually need the vis matrix. When a cell still has the old color you know it wasn't visited yet.

Also, you can avoid some of that code repetition by looping over the four directions:

void bfs( vector<vector<int>>& vis , vector<vector<int>>& image , int sr ,int sc, int newcolor, int ol) {
    pair<int,int> p = {sr, sc};
    queue<pair<int,int>> q;
    int width = image[0].size();
    int height = image.size();
    int dx[] = {-1, 1, 1, -1};
    int dy[] = { 0, 1,-1, -1};

    q.push(p);
    image[sr][sc] = newcolor;
    
    while (!q.empty()) {
        int x = q.front().first;
        int y = q.front().second;
        q.pop();
        
        for (int dir = 0; dir < 4; dir++) {
            x += dx[dir];
            y += dy[dir];
            if (x >= 0 && x < height && y >= 0 && y < width && image[x][y] == ol) {  
                image[x][y] = newcolor;
                q.push({x, y});
            }
        }
    }
}

vector<vector<int>> floodFill(vector<vector<int>>& image, int sr, int sc, int newColor) {
    vector<int> temp(image[0].size(),0);
    vector<vector<int>>vis(image.size(), temp);
    int ol = image[sr][sc];
    
    if (ol != newColor) bfs(vis, image, sr, sc, newColor, ol);
    return image;      
}