Выкладываю его сюда, так-как не нашел более подходящей ветки.
Это решение задачи, которое я не нашел в гугле, и мне пришлось ее решать самому)
выложенно для тех кто учит Теорию Алгоритмов
Задача
"ЗЕЛЕНЫЙ ШУМ - 2007". ЗАОЧНЫЙ ТУР ФЕСТИВАЛЯ ИНТЕЛЛЕКТУАЛЬНЫХ ИГР
ДОРОЖКА ДЛЯ РОБОТА
С произвольной белой клетки диаграммы проложите дорожку, идущую через все белые клетки. Дорожка может пересекать себя, но не должна дважды проходить через белый квадрат ни горизонтально, ни вертикально. Поворачивать на 90 градусов дорожка может, только дойдя до края поля или до черного квадрата. Конец дорожки должен упереться в край поля или черный квадрат. Через начальную точку не могут проходить никакие дополнительные (пересекающиеся) линии (в примере начальная точка обозначена кружком).
В ответе укажите координаты начальной и конечной точки и длину шага с поворотом от старта до финиша. Для приведенного примера ответ будет выглядеть так: старт 4/4, финиш 4/2, - 2R, 3L, 1L, 2L, 2L, 2R, 1R, 1.
Оценка: 120 баллов.
(так-же мне эта задача встретилась на РГР по Теории Алгоритмов)
Решение
Решение:
L-влево
R-вправо
U-вверх
D-вниз
(длинна пути указана без клетки в которой мы находимся)
START(3,5):3L,5R,1L,1U,3R,2U,3L,1U,2R,3D,4R,7U,1R, 3D,3L,2D,3R,1D,2L,5U,1L,1U,4L,1D,2R.(END(2,3))
|