Dfs on grid

what’s wrong in my implementation, please help me out on grid dfs
the problem link is :
https://www.codechef.com/LRNDSA08/problems/MARLA
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