For the risk problem in april starters I have written this code, it’s compiling successfully but not giving any output. Can anyone point out why, and also check if my function is correct (although I guess it is). Thanks very much if you spared a moment for this (I’m just a beginner )

#include <bits/stdc++.h>

using namespace std;

vector <vector> a;

int f(int x, int y)

{ int c=1;

```
a[x][y] = 0;
if(a[x][y+1]==1) {a[x][y+1]=0 ; c += f(x,y+1);}
if(a[x+1][y]==1) {a[x+1][y]=0 ; c += f(x+1,y);}
return c;
```

}

int main() {

```
int t; cin>>t;
while(t--)
{
int N,M;
cin>>N>>M;
for(int i=0;i<N;i++)
{
for(int j=0;j<M;j++)
cin>>a[i][j];
}
vector <int> d;
int l=0;
for(int i=0;i<N;i++)
{
for(int j=0;j<M;j++)
{
if(a[i][j]==1) {d[l]=f(i,j);l++;}
}
}
sort(d.begin(),d.end());
int b=0;
for(int i=0;i<d.size();i+=2)
b+=d[i];
cout<<b;
}
```

}

There’s no base case in your recursive function f ?

Hi! I wanted to ask that can it be done using multi source bfs?

Yes you can but that would unnecessarily overcomplicate the problem, a trivial dfs would suffice

1 Like

How would I need a base case, like I’m first calling it when my loop first detects a 1 in map, then I define c = 1 for it, and check ahead, defining and adding along and if the function terminates I return c.

Try dry running for some small case also there’s an out of bound issue in your code as you have not checked if x+1 < N and y+1<M while using these indices in the function f.

I checked it using && in the if clauses in the function (defining N and M as global) and for small value like N,M 4. No output is what’s bothering me. The code is evidently not being completed as even a hello is not printing if I write it on the last line.

#include <iostream.h>

#include <vector.h>

#include <algorithm.h>

using namespace std;

vector <vector> a;

int N,M;

int f(int x, int y)

{ int c=1;

```
a[x][y] = 0;
if(a[x][y+1]==1 && y+1<=M) {a[x][y+1]=0 ; c += f(x,y+1);}
if(a[x+1][y]==1 && x+1<=N) {a[x+1][y]=0 ; c += f(x+1,y);}
return c;
```

}

int main() {

```
int t; cin>>t;
while(t--)
{
cin>>N>>M;
cout<<N<<M;
for(int i=0;i<N;i++)
{
for(int j=0;j<M;j++)
cin>>a[i][j];
}
vector <int> d;
int l=0;
for(int i=0;i<N;i++)
{
for(int j=0;j<M;j++)
{
if(a[i][j]==1) {d[l]=f(i,j);l++;} cout<<l;
}
}
sort(d.begin(),d.end());
int b=0;
for(int i=0;i<d.size();i+=2)
b+=d[i];
cout<<b;
}
```

}

Okay hold on, the way you’re taking input is wrong you should take N Strings as the input. as when you do cin >> a[i][j] then it assumes “1001” as a single integer as there are no spaces between integers. Did you follow ?

Oh, Yeah got it.

Let me check.

Okay it worked thanks! Sorry for bothering

1 Like

I guess you are missing some degenerate case try all zeroes or ones in grid and check if the output is correct.