Динамическое программирование в электронных таблицах

Прекрасный яблоневый сад находится на поле размером N × N метров (1 < N < 30). Однажды ночью, когда яблоки уже созрели, разыгралась страшная буря, и яблоки разлетелись по всему полю. К счастью, фермер Василий создал робота, который умеет собирать яблоки. Исполнитель Василия Робот может перемещаться по полю, представляя, что каждый его метр равен одной клетке. За одно перемещение он может выполнить одну из двух команд: ВПРАВО или ВНИЗ. По команде вправо Робот перемещается в соседнюю правую клетку, по команде вниз — в соседнюю нижнюю. Поле ограничено внешним забором. На поле растут деревья, они на схеме поля выделены буквой Д. Через клетку с деревом Робот пройти не может. Перед запуском Робота в каждой клетке лежат яблоки в указанном количестве, от 1 до 100 штук. Посетив клетку, Робот забирает все яблоки в ней с собой; это также относится к начальной и конечной клеткам маршрута Робота.

Определите максимальное и минимальное количество яблок, которые может собрать Робот за один проход, пройдя из левой верхней клетки в правую нижнюю. Исходные данные представляют собой электронную таблицу размером N × N, каждая ячейка которой соответствует клетке квадрата. Деревья обозначены цветом и буквой Д.