Задание №18: Динамическое программирование (Робот в таблице)

(А. Богданов) Квадрат разлинован на N×N клеток (1 < N < 30). Роботу нужно перейти через поле с севера (верхняя строка) на юг (нижняя строка). Он может начать переход с любой клетки первой строки и закончить на любой клетке нижней строки. С каждым шагом Робот переходит в следующую строку и может за одно перемещение попасть в одну из трех клеток следующей строки (на клетку прямо вниз или на одну из клеток сле-ва/справа от неё). Ходы только влево или вправо (без смены строки), назад (в предыдущую строку),за границы поля и в цветные клетки запрещены. В каждой клетке поля лежит монета достоинством от 1 до 100. Робот собирает все монеты по пройденному маршруту. Определите максимальную и минимальную денежную сумму, которую может собрать Робот, пройдя с северной границы поля (сверху) до южной границы поля (снизу). В ответе укажите два числа: сначала максимальную сумму, затем минимальную.
Исходные данные для Робота записаны в файле 18-121.xls в виде прямоугольной таблицы, каждая ячейка которой соответствует клетке квадрата.