BFS "Digit Jump" 解决方案在机器上工作正常，在线判断得到 TLE

Question

此代码用于问题 DIGJUMP。

它为我尝试过的所有输入提供了正确的输出（我已经尝试了很多）。但问题是它在 codechef 上提交时得到 TLE。我检查了社论，相同的解决方案（概念方面）被接受，所以这意味着算法方法是正确的。一定是我实现有问题。

我试了很久，也没弄清楚是哪里出了问题

#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);

    vector<int> adj[10];
    for(int i = 0; i < len; i++)
        adj[str[i] - '0'].push_back(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);
        }

        size = adj[chi].size();
        for(int j = 0; j < size; j++)
        {
            if(visited[adj[chi][j]] == false)
            {
                tmpn.idx = adj[chi][j];
                tmpn.steps = steps + 1;
                que.push(tmpn);
            }
        }
    }
    return 0;
}

Answer 1

此解决方案无法在可接受的时间内完成该问题。请记住 BFS 是 O(E)。在具有 O(n) 某种数字的字符串中，这些数字之间有 O(n^2) 条边。对于 N=10^5 O(N^2) 太多了。

这需要一些优化，比如如果我们从一个相似的节点来到当前节点，我们就不会进一步跳到相似的节点。

BFS "Digit Jump" 解决方案在机器上工作正常，在线判断得到 TLE

BFS "Digit Jump" solution working fine on machine, get TLE on online judge

breadth-first-search

infinite-loop