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

*(Д. Статный) Квадрат разлинован на N×N клеток (1 < N < 30). Исполнитель Попрыгунчик может прыгать по клеткам, выполняя за одно перемещение одну из четырёх команд: вниз, вверх, вправо и влево. По команде вправо или влево Попрыгунчик перемещается в соседнюю правую или левую клетку соответственно, по команде вниз и вверх – в соседнюю нижнюю или верхнюю клетку соответственно. Команды вправо и влево доступны, когда нет возможности применить команды вверх и вниз. Проход по одним и тем же полям запрещен. Квадрат ограничен внешними стенами. Между соседними клетками квадрата также могут быть внутренние стены. Сквозь стену Попрыгунчик перепрыгнуть не может. Перед каждым запуском Попрыгунчика в каждой клетке квадрата лежит монета достоинством от 1 до 100. Посетив клетку, Попрыгунчик забирает монеты из полей; это также относится к начальной и конечной клеткам маршрута. Найдите максимальную и минимальную денежные суммы, которые может иметь Попрыгунчик, дойдя до середины поля (эта клетка выделена фоном) из верхней левой клетки.
Исходные данные записаны в файле 18-149.xls в виде прямоугольной таблицы, каждая ячейка которой соответствует клетке поля. В ответе укажите два числа – сначала максимальное значение, затем минимальное.