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.