Войти Регистрация
Алгоритмы

211. Меньше всего ретрансляций вдоль трассы

Средняя

Вдоль трассы стоят n вышек МТС по порядку. Вышка i может передать сигнал любой из следующих reach[i] вышек (с номерами от i + 1 до i + reach[i]); reach[i] = 0 — вышка только принимает.

Верните наименьшее число передач, чтобы сигнал от вышки 0 дошёл до вышки n − 1. Если дойти нельзя, верните −1. Для одной вышки ответ 0.

В работе: Резервный канал на трассе М‑4: при отказе магистрали связь идёт по радиорелейным пролётам, каждая передача добавляет задержку, и инженер выбирает маршрут с наименьшим числом пролётов.

Пример 1

Ввод
reach = [2, 3, 1, 1, 4]
Вывод
2

0 → 1 → 4: две передачи.

Пример 2

Ввод
reach = [3, 2, 1, 0, 4]
Вывод
-1

Все пути упираются в вышку 3.

Ограничения

  • 1 ≤ n ≤ 2·10⁵
  • 0 ≤ reach[i] ≤ 10⁵
  • Лимит — 2 с на тест (1500 мс).
Как вызывается ваш код Читать ввод и печатать ответ не нужно: мы вызываем функцию на каждом тесте и сравниваем то, что она вернула. print() и console.log() уходят в консоль. 
def min_relays(reach):
Жадный алгоритмBFSМассивцельO(n)

Источник: наша задача на данных МТС. Условие пересказано своими словами.