Квадрат разлинован на N×N клеток (1 < N < 30). Исполнитель Робот может перемещаться по клеткам, выполняя за одно перемещение одну из двух команд: влево или вниз. По команде влево Робот перемещается в соседнюю правую клетку, по команде вниз — в соседнюю нижнюю.
Квадрат ограничен внешними стенами. Между соседними клетками квадрата также могут быть внутренние стены. Сквозь стену Робот пройти не может.
Перед каждым запуском Робота в каждой клетке квадрата лежит монета достоинством от 1 до 200. Посетив клетку, Робот забирает монету с собой; это также относится к начальной и конечной клеткам маршрута Робота.
В «угловых» клетках поля — тех, которые справа и сверху ограничены стенами, Робот не может продолжать движение, поэтому накопленная сумма считается итоговой. Таких конечных клеток на поле может быть несколько, включая правую верхнюю клетку поля. При разных запусках итоговые накопленные суммы могут различаться.
Определите максимальную и минимальную денежные суммы среди всех возможных итоговых сумм, которые может собрать Робот, пройдя из правой верхней клетки в конечную клетку маршрута.
В ответе укажите два числа — сначала минимальную сумму, затем максимальную.
Исходные данные представляют собой электронную таблицу размером N × N, каждая ячейка которой соответствует клетке квадрата. Внутренние и внешние стены обозначены утолщёнными линиями.
Пример входных данных.
| 1 | 8 | 8 | 4 |
| 10 | 1 | 1 | 3 |
| 1 | 3 | 12 | 2 |
| 2 | 3 | 5 | 6 |
Ответ:
Сначала найдём максимальную денежную сумму. Для этого найдём максимальную денежную сумму для каждой ячейки таблицы. Скопируем границы и стенки на интервал А17:О31.
В ячейку О17 введем формулу:
=O1
Для каждой ячейки верхней строки это будет сумма всех ячеек справа от текущей.
В ячейку N17, введем формулу:
=O17+N1
Для каждой ячейки правого столбца это будет сумма всех ячеек снизу от текущей.
В ячейку О18, введем формулу:
=O17+O2
В ячейку N18 введем формулу:
=МАКС(O18;N17)+N2
и скопируем её на диапазон В30:О17.
Для ячеек у которых справа от них есть стена, их значение будет вычисляться как сумма текущей ячейки и ячейки выше.
Для таких ячеек из формулы уберем второе значение в функции МАКС.
Для ячеек у которых сверху от них есть стена, их значение будет вычисляться как сумма текущей ячейки и ячейки правее.
Для таких ячеек из формулы уберем первое значение в функции МАКС.
В тупиковых ячейках таблицы, из которых робот не сможет попасть (это ячейки D17, L19 и L27), поставим заведомо малое значение, например -10000.
Получим таблицу:
Робот может дойти до конечных ячеек: A31, D28 и E23.
Наибольшее среди ячеек - 3664.
Таким образом, получим значение максимальной денежной суммы — 3664.
Для нахождения минимальной суммы заменим значения МАКС на значение МИН с помощью окна "Найти и заменить".
В тупиковых ячейках таблицы, из которых робот не сможет попасть (это ячейки D17, L19 и L27), поставим заведомо большое значение, например 10000.
Получим таблицу:
Робот может дойти до конечных ячеек: A31, D28 и E23.
Наименьшее среди ячеек - 1139.
Таким образом, получим значение минимальной денежной суммы — 1139.
Ответ: 1139 3664.