Как оптимизировать BFS для «Минимального количества прыжков до конца посредством основной телепортации» (LeetCode 3629)? ⇐ Python

[Anonymous]

Я работаю над проблемой

3629. Минимальное количество прыжков для достижения цели через телепортацию Prime

И мое текущее решение - получить TLE (превышение лимита времени).
Мой текущий подход
Я использую:

• BFS для кратчайшего пути
• Проверка Prime во время обход
• Для каждого простого значения я сканирую весь массив, чтобы найти делимые числа

Упрощенный код

Код: Выделить всё

queue q;
vector vis(n, 0);

q.push(0);
vis[0] = 1;

while (!q.empty()) {
int i = q.front();
q.pop();

// adjacent moves
if (i + 1 < n && !vis[i + 1]) {
vis[i + 1] = 1;
q.push(i + 1);
}

if (i - 1 >= 0 && !vis[i - 1]) {
vis[i - 1] = 1;
q.push(i - 1);
}

// teleportation
if (isPrime(nums[i])) {
for (int j = 0; j < n; j++) {
if (j != i && nums[j] % nums[i] == 0 && !vis[j]) {
vis[j] = 1;
q.push(j);
}
}
}
}

Что я хочу понять

• Как можно оптимизировать эту BFS?
• Существует ли метод предварительной обработки с использованием:

• сито,
• prime факторы,
• хэш-карта/группировка,
  
  , позволяющая избежать повторного сканирования массива?

• Какова оптимальная временная сложность для решения этой задачи?

Я был бы признателен за объяснения структуры данных или подхода к графическому моделированию, а не только за окончательный код.