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

191. Сколько маршрутов у робота-доставщика

Средняя

Робот-доставщик Яндекса едет по кварталу, размеченному сеткой grid: строка — ряд клеток, '.' — проезд, '#' — перекрыто (стройка, ступеньки).

Робот стартует в левой верхней клетке, финиширует в правой нижней и за шаг сдвигается только вправо или вниз. Сколько разных маршрутов? Ответ может быть большим — верните его по модулю 10⁹ + 7. Если старт или финиш перекрыт, ответ 0.

В работе: Планировщик выбирает квартал для пилота: при одной стройке на углу у робота остаётся 0 маршрутов, а на сетке 600 × 600 перебор путей не закончится никогда.

Пример 1

Ввод
grid = ["...", ".#.", "..."]
Вывод
2

Центр перекрыт: только по краю сверху или снизу — 2 маршрута.

Пример 2

Ввод
grid = [".#", "#."]
Вывод
0

Из старта не выехать.

Ограничения

  • 1 ≤ h, w ≤ 1000
  • строки одной длины из символов . и #
  • Лимит — 2 с на тест (2000 мс).
Как вызывается ваш код Читать ввод и печатать ответ не нужно: мы вызываем функцию на каждом тесте и сравниваем то, что она вернула. print() и console.log() уходят в консоль. 
def robot_routes(grid):
Динамическое программированиеДП на сеткеМатрицацельO(n)

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