Please help me with this problem: Chef and Digit Jump

I was solving this question: http://www.codechef.com/problems/DIGJUMP

I used BFS but it is showing TLE. Can anyone help me optimize my code? Till now I don’t have any idea.

#include<iostream>
#include<fstream>
#include<algorithm>
#include<vector>
#include<set>
#include<map>
#include<cstdio>
#include<cstring>
#include<string>
#include<cstdlib>
#include<iomanip>
#include<queue>
#include<stack>
#include<cmath>
#include<utility>
using namespace std;

int main() {
           char temp[100005];
           scanf("%s",&temp);
           int a[strlen(temp)];
           int n = strlen(temp);
           for(int i = 0;i < n;i++) a[i] = temp[i] - '0';
           vector<int> indx[10];
           for(int i = 0;i < n;i++) indx[a[i]].push_back(i);
           int dis[n];
           for(int i = 0;i < n;i++) dis[i] = -1;
           dis[0] = 0;
           queue<int> bfs;
           bfs.push(0);
           int digvisit[10];
           for(int i = 0;i < 10;i++) digvisit[i] = 0;
           while(bfs.size() > 0) {
                            int q = bfs.front();
                            int d = dis[q];
                            queue<int> temp;
                            temp = bfs;
                            bfs.pop();
                            if(q == n-1) break;
                            if(q-1 >= 0) {
                                   if(dis[q-1] == -1) {
                                               dis[q-1] = d+1;
                                               bfs.push(q-1);
                                   }
                            }
                            if(q+1 < n) {
                                   if(dis[q+1] == -1) {
                                               dis[q+1] = d+1;
                                               bfs.push(q+1);
                                   }
                            }
                            int l = a[q];
                            for(int i = 0;i < indx[l].size();i++) {
                                    int lol = indx[l].at(i);
                                    if(dis[lol] == -1) {
                                                dis[lol] = d+1;
                                                bfs.push(lol);
                                    }
                            }
                            indx[l].clear();
                            label: ;
           }
           printf("%d\n",dis[n-1]);
           return 0;
}
1 Like

A good practice is to use !bfs.empty() instead of bfs.size() > 0.

1 Like

Thanks but that won’t answer the question.

I have removed two lines from your code and it’s accepted. http://www.codechef.com/viewsolution/5647934

4 Likes

Woah Thanks! I added that due to some previous code snippet but I removed it and forgot to remove this piece of code.