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

(А. Кабанов) Квадрат разлинован на N×N клеток (1 < N < 20). Исполнитель Буквоед может перемещаться по клеткам, выполняя за одно перемещение одну из двух команд: вправо или вниз. По команде вправо Буквоед перемещается в соседнюю правую клетку, по команде вниз – в соседнюю нижнюю. При попытке пересечь границы квадрата, обозначенные жирными линиями, Буквоед разрушается. В каждой клетке квадрата записано число от 10 до 99 или латинская буква P. Посетив клетку, Буквоед платит за её посещение, плата равна значению числа в клетке; это также относится к начальной и конечной точке маршрута. За посещение клетки P плата не взимается. Определите минимальную и максимальную плату, которую заплатит Буквоед, пройдя из левой верхней клетки в правую нижнюю, при этом маршрут должен проходить через две клетки P. В ответе укажите два числа – сначала минимальную, затем максимальную плату.
Исходные данные для Буквоеда записаны в файле 18-119.xls в виде прямоугольной таблицы, каждая ячейка которой соответствует клетке квадрата.