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

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