SPOJ ABCPath

general
, ,
1

Hi everyone I was trying to solve the problem on SPOJ : SPOJ.com - Problem ABCPATH
My submitted code that gives WA (used DFS) : https://ideone.com/k8CFG4
I cannot seem to understand where I am going wrong
One test case that the code fails is
5 5
AAABB
BBBBB
CDCDC
DDDDD
EEEEE

If anyone could guide me it would be very helpful. Do I need to make use of backtracking also because I guess it is why the answer is wrong, I tried to debug it but im stuck

1 Like
2

Hey man , first of all who r u ? means u r taking whole template of mine (khud ki hi bana lete bhai ) .

also we have to find max distance not max count.

    #include <bits/stdc++.h>
    using namespace std;
     
    #define lli long long int
    #define MAX 55
     
    #define loop(i,n)  for (lli i = 0; i < n; i++)
    #define FOR(i,a,b) for (lli i = a; i < b; i++)
     
     
    #define F first
    #define S second
    #define pii pair<lli,lli>
     
    #define mem0(a) memset(a,0,sizeof(a))
     
     
    int vis[MAX][MAX];
    lli arr[MAX][MAX];
    lli dist[MAX][MAX];
    lli N , M;
     
    bool is_valid(lli x , lli y)
    {
        if(x<1 or x>N or y<1 or y>M) 
            return false;
        
        if(vis[x][y]==1)
            return false;
        
        return true;
    }
     
     
    // directions
    int dx[] = {-1,1,0,0,-1,1,-1,1};
    int dy[] = {0,0,-1,1,-1,-1,1,1};
     
    lli cnt=0;
     
     
    lli BFS(lli srcX , lli srcY)
    {
        lli maxi= 1;
        vis[srcX][srcY]=1;
        dist[srcX][srcY]=1;
        
        queue<pii>q;
        q.push({srcX,srcY});
        
        while(!q.empty())
        {
            lli curX = q.front().F;
            lli curY = q.front().S;
            
            //cout<<curX<<" "<<curY<<endl;
            
            q.pop();
            
            for(lli i=0;i<8;i++) //in 8 direction
            {
                lli newX = curX + dx[i];
                lli newY = curY + dy[i];
                    
                if(is_valid(newX , newY) and arr[newX][newY] == arr[curX][curY]+1)
                {
     
                    vis[newX][newY] = 1;
                    dist[newX][newY] = dist[curX][curY]+1;
                    maxi = max(maxi , dist[newX][newY]);
                    
                    q.push({newX , newY});
                }
            }
        }
        return maxi;
        
    }
     
    int main()
    {
        lli qw=0;
        while(1){
            
            cin>>N>>M;
            if(N==0 and M==0)
                break;
                
            lli maxi =-1;
            
            mem0(vis);
            mem0(dist);
            mem0(arr);
            
            FOR(i,1,N+1)
            {
                FOR(j,1,M+1)
                {
                    char ch;
                    cin>>ch;
                    arr[i][j] = ch-'A'+1;
                }
            }
            
            FOR(i,1,N+1)
            {
                FOR(j,1,M+1)
                {
                    if(arr[i][j]==1)
                    {
                        mem0(vis);
                        mem0(dist);
                        maxi = max(maxi ,BFS(i,j));
                    }
                }
            }
            
            cout<<"Case "<<qw+1<<": ";
            if(maxi==-1)
                cout<<0<<"\n";
            else
                cout<<(maxi)<<"\n";
            qw++;
        } 
        
        return 0;
        
    }
2 Likes
3

okay thank you and I used your template because it was easily understandable I am just a beginner and your template was very helpful. I am sorry I will create a new one for my own use

1 Like
4

Actually i fear for plag so , u rewrite whole things in your way.

5

okay I am really sorry I did not know it would be an issue I will not use it any further… Thank you for the help and really sorry again

1 Like