Квадрат разлинован на N × N клеток (1 < N < 30). Исполнитель Робот может перемещаться по клеткам, выполняя за одно перемещение одну из двух команд: вправо или вниз. По команде вправо Робот перемещается в соседнюю правую клетку, по команде вниз — в соседнюю нижнюю. Квадрат ограничен внешними стенами.
Между соседними клетками квадрата также могут быть внутренние стены. Сквозь стену Робот пройти не может.
Перед каждым запуском Робота в каждой клетке квадрата лежит монета достоинством
Определите максимальную и минимальную денежные суммы, которые может собрать Робот, пройдя из левой верхней клетки в правую нижнюю. В ответе укажите два числа — сначала максимальную сумму, затем минимальную.
Исходные данные представляют собой электронную таблицу размером N × N, каждая ячейка которой соответствует клетке квадрата. Внутренние и внешние стены обозначены утолщёнными линиями
Пример входных данных:
| 1 | 8 | 8 | 4 |
| 10 | 1 | 1 | 3 |
| 1 | 3 | 12 | 2 |
| 2 | 3 | 5 | 6 |
Ответ:
Сначала найдём максимальную денежную сумму. Для этого найдём максимальную денежную сумму для каждой ячейки таблицы.
В ячейку B23 запишем формулу =B2+МАКС(B22;A23). Скопируем эту формулу во все ячейки в диапазоне B23:T41.
Для ячеек E28:E35, I31:I38, M31:M38, R28:R35, T23:T3, поскольку слева от них имеется внутренняя стенка, максимальная денежная сумма вычисляется как сумма текущей ячейки и суммы сверху. В ячейку E28 запишем формулу =E27+E7 и скопируем эту формулу во все ячейки в диапазоне E28:E35.
Для ячеек B23:F23, F25:J25, J27:N27, поскольку сверху от них имеется внутренняя стенка, максимальная денежная сумма вычисляется как сумма текущей ячейки и суммы слева.
Таким образом,
Аналогичным образом найдём значение минимальной денежной суммы.
Ответ: 2226 902.