Как решить задачу про черепашку?

Question

[kate]

Не могу понять, как решить, в интернете немного другие примеры...

Есть сетка, по которой может двигаться черепашка. Двигаться можно только по черным линиям. Черепашке необходимо попасть из пункта А в пункт Б. На каждом углу она может поворачивать только на Т1 или только Т2. Время движения по каждой улице указано в таблице. Требуется найти максимальное время, за которое черепашка может попасть из пункта А в пункт Б.
Произвести расчет на бумаге методом динамического программирования. Процесс вычисления представить в виде таблицы. Для второй сверху строки таблицы выписать подробный расчет.
Если А - левый верхний угол, Б - правый нижний угол. Т1- восток, Т2 - юг.

Comments

[Saboteur]

Насчитал вроде 15 вариантов. Просто вручную их пересчитайте и все.

[Сергей delphinpro]

Маршрут не существует.
Левые углы находятся в крайних западных направлениях. Конечная точка - на востоке. А черепаха не может двигаться на восток. Нестыковочка...

[Kolejium]

Меня вот тоже интересует, запад это поворот налево? Может T1, T2 это не запад и юг, а поворот относительно направления черепашки?

[Сергей delphinpro]

Kolejium, нет. просто формулировка задачи ошибочна, вместо востока, девушка написала запад =)

[profesor08]

А разве смысл таких задач не в том, чтоб решать их самостоятельно, чтоб заставить свои мозги шевелиться?

Answer 1

[Константин Цветков]

методом динамического программирования

То есть подзадача — прохождение перекрёстка и её рекурсивное выполнение начиная с пункта А.

Comments

[longclaps]

метод динамического программирования == рекурсия?
всёвыврёти

[Константин Цветков]

longclaps, Нет. Не ==.

Answer 2

[Kolejium]

Нашел я эту задачу в нормальном ввиде на cyberforum'e
www.cyberforum.ru/programming-theory/thread1455071.html
И решение готов подсказать))) https://ru.wikipedia.org/wiki/%D0%9F%D0%BE%D0%B8%D...
А вот решать нет уж)