Dfs on grid

problem code on codechef : MARLA

code:

`````` #include<iostream>
#include<vector>
#include<bits/stdc++.h>
#define ll long long
using namespace std;
ll n,m,a[1001][1001],cnt,mx,mn,s;
bool vis[1001][1001];
ll dx[]={1,-1};
ll dy[]={0,0};
bool isvalid(ll x, ll y,ll strength)
{
if(vis[x][y]==0 && a[x][y]==strength && x>=0 && x<n && y<m && y>=0)
{
return true;
}
else
{
return false;
}
}
void dfs(ll x , ll y)
{
s=a[x][y];
cnt++;
vis[x][y]=1;
for(ll i=0;i<2;i++)
{
if(isvalid(x+dx[i],y+dy[i],a[x][y]))
{
dfs(x+dx[i],y+dy[i]);
}
}
}
int main()
{
cin>>n>>m;
for(ll i=0;i<n;i++)
{
for(ll j=0;j<m;j++)
{
cin>>a[i][j];
}
}
mx=0;
mn=INT_MAX;
for(ll i=0;i<n;i++)
{
for(ll j=0;j<m;j++)
{
if(!vis[i][j])
{
cnt=0;
dfs(i,j);
mx=max(mx,cnt);
mn=min(mn,s);
}
}
}
cout<<mn<<" "<<mx;
return 0;
}
``````

In `isvalid`, you should check the first two conditions after the last four conditions.

Also, you need 4 directions for `dx` and `dy` - definitely don’t assume based on the sample that the components will have to be in the same row

Also, you can’t do `mx=max(mx,cnt);` if you change the minimum strength, you have to set `mx` to whatever `cnt` is since the old values for `mx` aren’t valid anymore.

1 Like

thanks for the help