Вопрос :
Найдите количество различных кратчайших путей от точки A до точки B в городе с идеально горизонтальными улицами и вертикальными проспектами, как показано на рисунке ниже. Никакой путь не может пересекать огороженную территорию, показанную на рисунке серым цветом.
Решение :
Ответ - 17 путей.
Самый простой способ получить это - применить динамическое программирование - одну из стратегий разработки алгоритмов, обсуждаемых в первом руководстве. Этот подход определяет количество кратчайших путей от точки A до каждого перекрестка в сетке за пределами огороженной зоны (см. Рисунок ниже). Начиная с присвоения 1 пересечению A, эти числа можно вычислять построчно и слева направо в каждой строке. Если у перекрестка есть и левые, и верхние соседи, его номер вычисляется как сумма соседних чисел; если у перекрестка есть только один из таких соседей, он получает тот же номер, что и у соседа.
Спасибо за чтение
Placewit воспитывает лучших инженеров, предоставляя интерактивные занятия в классе и помогая им развивать свои навыки и трудоустроиться в удивительных компаниях.
Узнайте больше на Placewit. Следите за нами в Instagram и Facebook для ежедневного обучения.
