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

104. Курьер с пропусками в бизнес-центре

Сложная

Курьер Яндекс Еды несёт заказ по этажу бизнес-центра. План — список строк grid одинаковой длины: S — вход, E — офис клиента, # — стена, . — проход, a–d — посты охраны, где выдают пропуск своего цвета, A–D — турникеты, которые пропускают только с пропуском того же цвета.

За шаг курьер переходит в соседнюю клетку по стороне. Пропуск, взятый на посту, остаётся у курьера до конца. Верните наименьшее число шагов от S до E или -1, если до клиента не дойти.

В работе: Оценка времени «от двери до двери» в больших БЦ, где курьер теряет 5–10 минут на поиск нужного поста охраны.

Пример 1

Ввод
grid = ["S.A.E", ".####", "a...."]
Вывод
8

Сначала вниз за пропуском a (2 шага), обратно к S (2), затем через турникет A к E (4) — итого 8.

Пример 2

Ввод
grid = ["S#E"]
Вывод
-1

Стена — пути нет.

Ограничения

  • 1 ≤ число строк, длина строки ≤ 250
  • ровно одна S, хотя бы одна E
  • пропуски только a–d, турникеты A–D
  • Лимит — 3 с на тест (3000 мс).
Как вызывается ваш код Читать ввод и печатать ответ не нужно: мы вызываем функцию на каждом тесте и сравниваем то, что она вернула. print() и console.log() уходят в консоль. 
def courier_steps(grid):
ГрафыBFS на сеткеБитовая маска состоянияцельO(n)

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