Home > Net >  Stack in cpp is creating infinity loop
Stack in cpp is creating infinity loop

Time:11-10

vector<vector<int>> floodFill(vector<vector<int>>& image, int sr, int sc, int color) {
    int prevColor = image[sr][sc];
    int m = image.size();
    int n = image[0].size();
    image[sr][sc] = color;
   
    stack <pair<int, int>> positionToVisit; 
    positionToVisit.push({sr, sc});

   int t = 3000;  
    while (!positionToVisit.empty() && t--) {  //There is a problem I couldn't solve, except giving t is getting time limit error
        
        if (sr>0 && image[sr-1][sc] == prevColor ) {
            image[sr-1][sc] = color;
            positionToVisit.push({sr-1, sc});
        }
        if (sr<m-1 && image[sr 1][sc] == prevColor ) {
            image[sr 1][sc] = color;
            positionToVisit.push({sr 1, sc});
        }

        if (sc>0 && image[sr][sc-1] == prevColor ) {
            image[sr][sc-1] = color;
            positionToVisit.push({sr, sc-1});
        }
        if (sr<n-1 && image[sr][sc 1] == prevColor ) {
            image[sr][sc 1] = color;
            positionToVisit.push({sr, sc 1});
        }
        
        sr = positionToVisit.top().first;
        sc = positionToVisit.top().second;
        
        image[sr][sc] = color;
        positionToVisit.pop();

    }

    return image;
}

If I don't use the 't' variable in the while() condition, it falls in time limit exceeded and it is not stopping when stack getting empty and continuing infinity loop. But when I'm using t here it immediately breaks when the stack is being empty. I couldn't figure out the problem.

CodePudding user response:

That code looks correct except

if (sr<n-1 && image[sr][sc 1] == prevColor )

should be

if (sc<n-1 && image[sr][sc 1] == prevColor )

CodePudding user response:

You should also add this check to the beginning of your function.

if(color == prevColor) {
  return image;
}
  • Related