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.