Задание на выходные ;)

[BadBlock]

В 1993 году на областной олимпиаде мне довелось на MSX-Бейсике решать такую задачу:

"Имеется таблица размером N на N, заполненная числами. Исполнитель изначально находится в ячейке (1,1), в северо-западном углу таблицы. Он двигается от северо-западного угла таблицы к юго-восточному углу, по пути "собирая" числа в ячейках, в которых он находится, и складывая их между собой. За каждый ход Исполнитель может перейти на соседнюю ячейку: либо на восток (В), либо на юг (Ю). Программа дожна определить маршрут от ячейки (1,1) до ячейки (N,N), при котором набранная сумма будет наибольшей, и вывести маршрут в виде последовательности типа ВВЮВЮЮВВВ. Число N и содержимое ячеек вводятся с клавиатуры".

Если есть желание, решайте, а я пока поищу листочек с распечаткой своего тогдашнего решения.

[Oigen McPine]

Решил?

[BadBlock]

Решил, часа за два написал и отладил.

[Oigen McPine]

Готово! Нарисовал алгоритм! А как известно - грамотный алгоритм - 90% успеха.

[BadBlock]

Колись, в чем суть!

[Oigen McPine]

Очень просто.
Следует сделать бинарное дерево со всеми вариантами, и выбрать с наибольшей суммой.

[BadBlock]

Прикол в том, что я там как-то обошелся без деревьев, без рекурсии –
белый был, наверное, совсем горячий, вот только никак не могу найти распечатку.

[Oigen McPine]

Хм. Интернетсво.
Ищи распечатку... или вспоминай!

[Div]

А может тебе все это в горячечном бреду предвиделось

[BadBlock]

> или вспоминай!

Никак пока...

> может тебе все это в горячечном бреду предвиделось

Угу, мне эту задачу на олимпиаде зачли как решенную тоже в горячечном бреду?

[Nook]

эээ
Отцы!!!
Код в студию плиз...

[Nook]

Вы чего не отвечаете? гордые что-ли такие

[BadBlock]

Я потерял свой, получается.
Давно дело было.
Надо еще в одном месте пошукать на досуге, может, найду.