CODEWITHSUNDEEP
c++recursion
Rajat Sharma
Rajat Sharma

Reputation: 21

Looking for a recursive solution to the problem given below

I want to find the longest island where "1" represents land and "0" represent water. Furthermore, i want to do it using a recursive solution. I am getting a stack overflow error. Is something wrong with the function calling??

int ans;
vector<vector<int>> dir = {{-1, 0}, {0, -1}, {1, 0}, {0, 1}};

void calcarea(vector<vector<int>> grid, int r, int c, int m, int n, int ans)
{
    for(auto &d : dir)
    {
        int t1, t2;
        t1 = r + d[0];
        t2 = c + d[1];
        if(t1 >= 0 && t1 < m && t2 >= 0 && t2 < n)
        {
            if(grid[t1][t2] == 1)
            {
                ans += 1;
                calcarea(grid, t1, t2, m, n, ans);
            }
        }
    }
}

int maxAreaOfIsland(vector<vector<int>>& grid) {
    int m = grid.size();
    int n = grid[0].size();
    int output = 0;
    
    for(int i = 0; i < m; i++)
    {
        for(int j = 0; j < n; j++)
        {
            if(grid[i][j] == 1)
            {
                ans = 1;
                calcarea(grid, i , j, m, n, ans);
                output = max(output, ans);
            }
        }
    }
    return output;
}

Upvotes: 2

Views: 39

Answers (1)

Idan
Idan

Reputation: 202

You need to mark the place as "visited" so you won't check it again. You can do something like this in the calcarea function:

if(grid[t1][t2] == 1)
{
    grid[t1][t2] = 0; // add this
    ans += 1;
    calcarea(grid, t1, t2, m, n, ans);
}

Upvotes: 1

Related Questions