Need help in ABCPATH spoj problem

Problem link:- https://www.spoj.com/problems/ABCPATH/

I tried dfs on grid and memoized the solution but this is getting wrong somewhere. Can you help please.

My solution:-

#include <bits/stdc++.h>
using namespace std;
#define nl "\n"

int n,m,x,y,rr;
char a[55][55];
int dp[55][55];


int dx[] = {-1,-1,0,1,1,1,0,-1};
int dy[] = {0,1,1,1,0,-1,-1,-1};

bool isValid(int fx, int fy, char cp)
{
	cp++;
	if(fx<0||fx>=n||fy<0||fy>=m) return false;
	if(a[fx][fy]!=cp) return false;
	
	return true;
}

int dfs(int sx, int sy)
{
	if(dp[sx][sy]!=-1) return dp[sx][sy];
	
	int pp=1;
	
	int df = 0;
	
	for(int i=0; i<8; i++)
	{
		int nx = sx+dx[i];
		int ny = sy+dy[i];
		
		if(isValid(nx,ny,a[sx][sy]))
		{
			int rp = dfs(nx,ny);
			df = max(df,rp);
		}
	}
	pp+=df;
	return dp[sx][sy] = pp;
	
}

int main () {
	ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);	
//    freopen("input.txt", "r", stdin);
		int pp=1;
		while(1)
		{
			
			cin>>n>>m;
			if(n==0 && m==0) break;
			
			memset(dp,-1,sizeof(dp));
			vector<pair<int,int> > p;
			p.clear();
			
			int ans=0;
			for(int i=0; i<n; i++)
			{
				for(int j=0; j<m; j++)
				{
					cin>>a[i][j];
					if(a[i][j]=='A') p.push_back({i,j});
				}
			}
			if(p.size()==0)
			{
				cout<<ans<<nl;
				continue;
			}
			for(int i=0; i<p.size(); i++)
			{
				
				rr = dfs(p[i].first,p[i].second);
				ans = max(ans,rr);
			}
			cout<<"Case "<<pp++<<": "<<ans<<nl;
		}
 		
return 0;
}

First , please format your code by ``` before and after code.

done. please have a look.

I m not able to understand input pattern and output means what we wanna do.

got it .

If you have performed dfs for first a then why are you not clearing value of dp?
I have performed bfs.

Code
#include<bits/stdc++.h>
using namespace std;
using lld=long long int;

lld vis[10001];
lld res[10001];
vector <int> lst[10001];

int x[]={-1,-1,-1,0,1,1,1,0};
int y[]={-1,0,1,1,1,0,-1,-1};

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    int h,w;
    cin>>h>>w;
    int t=0;
    while(h!=0)
    {
        t++;
        string s;
        s="";
        int arr[h+1][w+1];
        int vis[h+1][w+1],res[h+1][w+1];
        for(int i=1;i<=h;i++)
        {
            cin>>s;
            for(int j=1;j<=w;j++)
            {
                arr[i][j]=s[j-1]-'A'+1;
                vis[i][j]=0;
                res[i][j]=-1;
            }
        }
        int mx=0,fimax=0;
        for(int i=1;i<=h;i++)
        for(int j=1;j<=w;j++)
        {
            mx=0;
            if(arr[i][j]==1)
            {
                int a=i,b=j;
                mx=1;
                queue <pair<int,int> >q;
                q.push(make_pair(a,b));
                vis[a][b]=1;
                res[a][b]=1;
                while(!q.empty())
                {
                    pair <int,int> p;
                    p=q.front();
                    a=p.first;  b=p.second;
                    //cout<<a<<" "<<b<<endl;
                    q.pop();
                    for(int n = 0; n < 8; n++)
                    {
                        int f=a+x[n],s=b+y[n];
                        if(f>0&&f<=h&&s>0&&s<=w&&vis[f][s]==0&&arr[f][s]==arr[a][b]+1)
                        {
                            vis[f][s]=1;
                            res[f][s]=res[a][b]+1;
                            if(res[f][s]>mx)
                            mx=res[f][s];
                            q.push(make_pair(f,s));
                            //cout<<mx<<"V"<<f<<"V"<<s<<endl;
                        }
                    }
                }
                if(mx>fimax)
                fimax=mx;
                
            }
        }
        cout<<"Case "<<t<<": ";
        cout<<fimax<<"\n";
        cin>>h>>w;
    }
}
1 Like

Yes, after each call of dfs function clear dp by -

#define mem0(a) memset(a,0,sizeof(a))

mem0(dp);
for(int i=0; i<p.size(); i++)
			{
				
				rr = dfs(p[i].first,p[i].second);
                                //clear_DP
				ans = max(ans,rr);
			}
1 Like

BFS is more easier , and easy to debug .

Yeah, I always prefer bfs over dfs

@ssrivastava990 @sebastian I cleared the dp in my code but again WA. But what is the point of memoization if i clear the dp again and again.

whats your answer in
1 1
A
0 0

1

Your point is correct. You do not need to clear dp

Why ?

he assign this value to dp now for each call whole dp must be filled with -1.

Say there are 2 A. Now for first A, we have already stored the value in dp when we get B in array. For second A, if we reach same B then we can directly return its value.

2 2
AB
CB
What is o/p?

It’s correct. 3