Need help in ABCPATH spoj problem

[satyam_656]

Problem link:- SPOJ.com - Problem 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;
}

[ssrivastava990]

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

[satyam_656]

done. please have a look.

[ssrivastava990]

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

[ssrivastava990]

got it .

[sebastian]

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;
    }
}

[ssrivastava990]

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

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

mem0(dp);

[ssrivastava990]

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

[ssrivastava990]

BFS is more easier , and easy to debug .

[sebastian]

Yeah, I always prefer bfs over dfs

[satyam_656]

@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.

[ssrivastava990]

whats your answer in
1 1
A
0 0

[satyam_656]

1

[sebastian]

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

[ssrivastava990]

Why ?

@satyam_656

return dp[sx][sy] = pp;

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

[sebastian]

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.

[sebastian]

2 2
AB
CB
What is o/p?

[satyam_656]

It’s correct. 3

[anon43022059]

‘’’// #pragma GCC optimize(“Ofast,unroll-loops”)

// #pragma GCC target(“sse,sse2,sse3,ssse3,sse4,popcnt,mmx,avx,avx2”)

#include <bits/stdc++.h>

#define ll long long

#define ull unsigned long long

#define lld long double

#define w(x) ll x;cin>>x;while(x–)

#define all(x) x.begin(), x.end()

#define db(x) (cout<<#x<<":"<<(x)<<’\n’)

#define lb lower_bound

#define ub upper_bound

#define gcd(a,b) __gcd(a,b)

#define lcm(a,b) __detail::__lcm(a,b)

#define speed ios_base::sync_with_stdio(false), cin.tie(nullptr)

using namespace std;

const lld pi=3.141592653589;

const ll mod=1000000007;

const ll maxn=51;

template

void printv(const vector& v) { for(auto i:v) cout<<i<<’ ‘; cout<<’\n’; }

template

void printv(const vector<pair<T, T>>& v) { for(auto p:v) cout<<"("<<p.first<<","<<p.second<<"),"; cout<<’\n’; }

ll n,m;

vector<vector> a(maxn,vector(maxn,’-’));

ll dp[maxn][maxn];

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

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

bool valid(ll i,ll j,ll x,ll y){

if(i<0||i>=n||j<0||j>=m||(a[i][j]!=a[x][y]+1)){

    return false;

}

return true;

}

ll dfs(ll x,ll y){

ll &res=dp[x][y];

if(res!=-1){

    return res;

}

ll ans=0;

for(ll t=0;t<8;t++){

    if(valid(x+dx[t],y+dy[t],x,y)){

        ans=max(ans,dfs(x+dx[t],y+dy[t]));

    }

}

ans+=1;

return res=ans;

}

int main(){

speed;

//freopen("input.txt","r",stdin);

//freopen("output.txt","w",stdout);

ll T=1;

while(true){

    cin>>n>>m;

    if(n==0&&m==0)  break;

    for(ll i=0;i<n;i++){

        for(ll j=0;j<m;j++){

            cin>>a[i][j];

        }

    }

    ll ans=0;

    for(ll i=0;i<n;i++){

        for(ll j=0;j<m;j++){

            if(a[i][j]=='A'){

                memset(dp,-1,sizeof dp);

                ans=max(ans,dfs(i,j));

            }

        }

    }

    cout<<"Case "<<T<<": "<<ans<<'\n';

    T++;

    for(ll i=0;i<maxn;i++){

        for(ll j=0;j<maxn;j++){

            a[i][j]='-';

        }

    }

}

return 0;

}’’’