Search code examples
c++recursiongraphdepth-first-search

Anyone can tell me why it is giving runtime error


Question Link: LeetCode, I am getting runtime error but not found where it is causing. Why it is giving runtime error any one can explain it to me?

class Solution {
public:
    bool dfs(vector<vector<int>>& grid, int row, int col, int color)
    {
        if(row<0 || col<0 || row>=grid.size() || col>=grid[0].size() || abs(grid[row][col])!=color)
            return false;
        grid[row][col]=-color;
        bool first = dfs(grid, row-1, col, color);
        bool second = dfs(grid, row, col+1, color);
        bool third = dfs(grid, row+1, col, color);
        bool fourth = dfs(grid, row, col-1, color);
        if(first && second && third && fourth)
        {
            grid[row][col]=color;
        }
        return true;
    }
    vector<vector<int>> colorBorder(vector<vector<int>>& grid, int row, int col, int color) {
        
        dfs(grid, row, col, grid[row][col]);
        for(int i=0; i<grid.size(); i++)
        {
            for(int j=0; j<grid[0].size(); j++)
            {
                if(grid[i][j]<0)
                    grid[i][j]=color;
            }
        }
        return grid;    
    }
};

Solution

  • I've wrote test for your code: https://godbolt.org/z/TazozK8xe and enabled address sanitizer.

    Without reading your code and just by reading sanitizer logs you can see you have infinitive recursion (note number of stack frames is more then 178, when problem is simple to do it in maximum 4 steps). Basically your condition to stop recursion is wrong or incomplete.

    I recommend you to learn how to use debugger so you can easier understand this issue.