# RISK Problem (April Starters)

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.