I got runtime error while using dfs Algorithm

Question

I got a runtime error while using dfs for a problem.

Here is the error:

AddressSanitizer: stack-overflow on address 0x7ffce7e6eff8 (pc 0x000000359715 bp 0x7ffce7e6f040 sp 0x7ffce7e6f000 T0

Here is the question link:

(https://leetcode.com/problems/flood-fill/)

And here is my code:

class Solution {
public:
    vector<vector<int>> floodFill(vector<vector<int>>& image, int sr, int sc, int newColor) {

        int color=image[sr][sc];
        dfs(image,sr,sc,color,newColor);
        return image;
    }

    void dfs(vector<vector<int>> &image,int sr,int sc,int color,int newcolor)
    {
         if(sr<0 || sr>=image.size() || sc<0 || sc>=image[0].size() || image[sr][sc]!=color)
        {
            return;
        }

            image[sr][sc]=newcolor;
            dfs(image,sr,sc+1,color,newcolor);
            dfs(image,sr,sc-1,color,newcolor);
            dfs(image,sr+1,sc,color,newcolor);
            dfs(image,sr-1,sc,color,newcolor);

    }


};

It failed on the following test case:

[[0,0,0],[0,1,1]] 1 1 1

I am not able figure it out where I went wrong.

Thanks.

Answer 1

Check that newColor != color, otherwise you have infinite recursion, as you rely on the color change to avoid revisiting previously visited pixels.

This is precisely what happens with your failing test case.