# This simple BFS solution is giving TLE. I guess there might be some infinite loop, but don't know why.

here is the problem

``````#include <string.h>
#include <vector>
#include <queue>
#include <stdio.h>

using namespace std;

class Node
{
public:
int idx, steps;
};

int main()
{
char str[100001];
scanf("%s", str);
int len = strlen(str);

for(int i = 0; i < len; i++)

int idx, chi, size, steps;
Node tmpn;
tmpn.idx = 0;
tmpn.steps = 0;
queue<Node> que;
que.push(tmpn);
bool * visited = new bool[len];
for(int i = 0; i < len; i++)
visited[i] = false;

while(!que.empty())
{
tmpn = que.front();
que.pop();
idx = tmpn.idx;
steps = tmpn.steps;
chi = str[idx] - '0';

if(visited[idx])
continue;
visited[idx] = true;

if(idx == (len - 1))
{
printf("%d\n", tmpn.steps);
return 0;
}

if(visited[idx + 1] == false)
{
tmpn.idx = idx + 1;
tmpn.steps = steps + 1;
que.push(tmpn);
}

if(idx > 0 && visited[idx - 1] == false)
{
tmpn.idx = idx - 1;
tmpn.steps = steps + 1;
que.push(tmpn);
}

for(int j = 0; j < size; j++)
{
{
tmpn.steps = steps + 1;
que.push(tmpn);
}
}
}
return 0;
}
``````

Your solution wont finish in acceptable time for the problem. Remember that BFS ist O(E). In a string with O(n) digits of some kind there are O(n^2) edges between those digits. For N=10^5 O(N^2) is too much.

1 Like

Thanks. I kept thinking that maybe my code is entering an infinite loop for some test case

//