Chef and Digit Jumps : getting wrong answers

i am getting wrong answer but passing the sample cases;
problem : [chef and digit jumps](https://www.codechef.com/LRNDSA08/problems/DIGJUMP)

#include <bits/stdc++.h>
using namespace std;
class Graph
{ public:
    map<int,list<int>> l;
    void addedge(int x ,int y)
    {
        l[x].push_back(y);
    }
    void print()
    {
        for(auto node_pair : l)
        {
            cout<<node_pair.first<<"->";
            for(auto ngh: l[node_pair.first])
            {cout<<ngh<<" , ";}
            cout<<endl;
        }
    }
    int bfs (int src,int dest)
    {// cout<<"s"<<src<<" "<<"d"<<dest<<endl;
        map<int,int> dist;
        queue<int> q;
       
        for( auto node_pair : l)
        { int node = node_pair.first;
            dist[node]=INT_MAX;
        }
        dist[src]=0;
         q.push(src);
        while(!q.empty())
        {
            int n = q.front();
            q.pop();
            for(int ngh : l[n])
            {
                if(dist[ngh]==INT_MAX)
                {q.push(ngh);
                    dist[ngh]=dist[n]+1;}
            }
        }
       /* for(auto node_pair: l)
        {
            int node= node_pair.first;
            cout<<node<<" "<<dist[node]<<endl;
        } */
        return dist[dest];
    }

    
};


int main() {
    string str;
    cin>>str;
    Graph g;
  
    int i;
    vector<int> s;
    for(i=0;i<str.length();i++)
    {
        int x= str[i]-'0';
        s.push_back(x);
    }
    
    for( i =0;i<s.size();i++)
    {  
     if(i>0)
      {  if(g.l.find(s[i])!=g.l.end())
        { auto it =g.l.find(s[i]);
          s[i]= s[i]+10;
        
            g.addedge((it->first),s[i]);}
            g.addedge(s[i-1],s[i]);}
        
    }
    g.addedge(s[i-1],100);
   // g.print();
   // cout<<"x "<< x<<endl;
   int x = s.size();
    int ans= g.bfs(s[0],s[x-1]);
    cout<<ans<<endl;
	// your code goes here
	return 0;
}

i am getting wrong solution too.
my solution
Can someone help?

Anyway,
in your solution are you checking the adjacent elements?

i am connecting adjacent elements in the graph. i have tried many testcases and it seems to work fine.

Bumping this post up with my explanation.
I performed BFS by coverting the string into a graph and pushing them into a hashmap.
I started my bfs from source and used a distance vector to keep track of the nearest distance.
first i added the neighbours into the queue and then added the indices whose number were same as the number which was taken out of the queue. Then i deleted the vector of indices from the map so as to not repeat traversing it again.Once the graph touched the last vertex or end of string i stopped my BFS and printed out the distance.

1 Like

First of all an important observation in this problem is that the answer is never more than 19.
A BFS solution will work but a modified one, or simply a dijkstra solution in enough for solving the problem.
So you need to modify your solution such that you don’t visit the node with same value more than twice.

2 Likes