Runtime Error in DFS Solution


#1

Getting runtime error.

bool isValid(int x, int y, int n, int m, vector<vector<int>> &A)
{
    if(x<0 || y<0 || x>=n || y>=m) return false;
    if(A[x][y] == 0) return false;
    return true;
}

int dfs(int x, int y, int n, int m, vector<vector<int>> &A)
{
    if(!isValid(x,y,n,m,A)) return 0;
    A[x][y]=0;
    int ans = -1;
    vector<vector<int>> toVisit = {{1,0},{-1,0},{0,1},{0,-1},{1,1},{1,-1},{-1,1},{-1,-1}};
    for(int i=0; i<8; i++)
    {
        ans = max(ans, dfs(x+toVisit[i][0], y+toVisit[i][1], n, m, A));
    }
    return ans+1;
}


int Solution::solve(vector<vector<int> > &A)
{
    int n = A.size();
    int m = A[0].size();
    int ans = -1;
    for(int i=0; i<n; i++)
    {
        for(int j=0; i<m; j++)
        {
            if(A[i][j] == 1)
                ans = max(ans, dfs(i, j, n, m, A));
        }
    }
    return ans;
}

#2

You also need to keep track of the entries in the matrix that you have already visited, otherwise you will have unending recursive calls.