Задание

Квадрат разлинован на N × N клеток (1 < N < 30). Исполнитель Робот может перемещаться по клеткам, выполняя за одно перемещение одну из двух команд: вправо или вниз. По команде вправо Робот перемещается в соседнюю правую клетку, по команде вниз – в соседнюю нижнюю. Квадрат ограничен внешними стенами. Между соседними клетками квадрата также могут быть внутренние стены. Сквозь стену Робот пройти не может. Перед каждым запуском Робота в каждой клетке квадрата лежит монета достоинством от 1 до 100. Посетив клетку, Робот забирает монету с собой; это также относится к начальной и конечной клеткам маршрута Робота.

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

Пример входных данных:

Задание выполняется с использованием прилагаемых файлов.

Разбор примера входных данных

Все картинки кликабельны!

Давайте на примере рассмотрим что необходимо делать роботу, чтобы собрать максимальную (минимальную) сумму, роботу нужно пройти из левой верхней клетки в правую нижнюю.

Ходить робот начинает из ячейки А1. Сделав ход вправо он попадет в ячейку В1, вниз - А2. В ячейках В1 и А2 накопятся суммы - 9 (1+8) и 11 (1+10) соответственно.

Очевидно, что в ячейку С1 робот сможет попасть из В1, в D1 из С1, А3 из А2, а в А4 из А3. За каждый ход робот будет накапливать соответствующие суммы.

На данном этапе необходимо остановиться и определиться, какую сумму будет собирать робот - максимальную или минимальную. От этого решения зависят дальнейшие ходы робота. Начнем с максимальной суммы.

В ячейку В2 робот может перейти двумя способами: из В1 и из А2. Т.к. в итоге в ячейке В3 должна получится максимальная сумма из двух возможных (В1+В2 = 9, А2+В2 = 11), то необходимо совершить ход из ячейки А2.

Аналогичным образом поступаем с ячейками C2 и D2.

В ячейку В3 робот может попасть из ячейки А3. С ячейкой С3 ситуация обстоит иным образом. Между ячейками С2 и С3 стоит стена, проходя через которую робот разрушается. Поэтому один единственный возможный ход в ячейку С3 из В3.

С ячейками D3, В4, С4 и D4 поступаем также как и с ячейками B2, C2 и т.д. 

Таким образом, максимальная сумма, которую может собрать робот равна 38.

 По аналогии найдем наименьшее значение.

Для воспроизведения кликните по картинке. 

Решение

Все картинки кликабельны!

Поле, на котором будет перемещаться Робот, имеет следующий вид.

Скопируем имеющееся поле и вставим его ниже через 2-3 строки. Изменим цвет фона ячеек для из выделения и очистим содержимое ячеек. Это будет то поле, где мы будем собирать сумму по условию. Обратите внимание на то, чтобы внутренние стены были отображены на поле.

Таким образом, исходное поле со значениями занимает диапазон A1:T20,  рабочее поле - А23:Т42. 

Скопируем в ячейку А23 значение из ячейки А1 или сделаем ссылку на ячейку А1, записав я ячейке А23 формулу: =A1. В ячейку B2 запишем формулу: =A23+B1. 

Скопируем эту формулу в диапазон C23:T23. Т.к. изначально в формуле ссылки на ячейки были относительными, то при копировании они автоматически изменят свои значения.

Аналогичным образом поступаем со столбцом А. В ячейку А24 запишем формулу: =A23+A2. Затем скопируем ее в диапазон А25:А42. Т.к. ссылки на ячейки были относительными, то при копировании они автоматически изменят свои значения.

Следующим этапом является сбор Роботом максимальной или минимальной суммы.

Начнем с максимальной суммы.

В ячейку В24 запишем формулу =МАКС(B23+B2;A24+B2). Затем скопируем эту формулу в диапазон В24:Т42.

ВНИМАНИЕ!

Указанную формулу нельзя копировать в диапазоны G26:G37 и L40:Q40. Ячейки этих диапазонов имеют внутренние стенки, проходя через которые Робот разрушится.

В ячейку  G26 необходимо записать формулу =G4+G25 и скопировать ее в диапазон G27:G37.

В ячейку L40 необходимо записать формулу =L18+K40 и скопировать ее в диапазон N40:Q40.

После заполнения всех ячеек квадрата, в ячейке T42 будет стоять максимальная денежная сумма, которую может собрать Робот - 721.

Аналогичным образом определяем минимальную сумму. В этом случае формула в ячейке В24 будет иметь вид =МИН(B23+B2;A24+B2). Затем эту формулу копируем в диапазон В24:Т42.

В диапазонах G26:G37 и L40:Q40 формулы не меняем.

После заполнения всех ячеек квадрата, в ячейке T42 будет стоять минимальная денежная сумма, которую может собрать Робот - 640.

Ответ: 721 640.