18. Исполнитель Робот: Квадрат разлинован на N× N клеток (1<N<26)
Квадрат разлинован на $N\times N$ клеток ($1<N<26$). Исполнитель Робот может перемещаться по клеткам, выполняя за одно перемещение одну из двух команд: вправо или вниз. По команде вправо Робот перемещается в соседнюю правую клетку; по команде вниз – в соседнюю нижнюю. Робот разрушается при попытке выхода за границу квадрата или при попытке пересечения стены клетки. В таблице стены отмечены границами с утолщением.
Перед запуском Робота в каждой клетке квадрата указан бонус, который Робот забирает после посещения клетки. Размер бонуса в каждой клетке – это натуральное число, не превышающее $100$. Это правило относится к начальной и конечной клеткам маршрута Робота.
Определите минимальную и максимальную суммы бонусов, которые может собрать Робот, перемещаясь из левой верхней клетки квадрата в его правую нижнюю клетку. В ответе укажите два числа без пробелов: сначала минимальную сумму, затем максимальную.
Исходные данные представлены в форме электронной таблицы размером $N\times N$, в которой одна ячейка соответствует одной клетке квадрата. Стены, через которые Роботу нельзя проходить, отмечены в электронной таблице границами с утолщением.
Пример входных данных:

Для указанных входных данных ответом является пара чисел: $27$, $41$.
В исходном файле таблица занимает диапазон A1:O15, поэтому размер квадрата равен $N=15$.
Внутренних стен в данной таблице нет, поэтому в каждую клетку, кроме клеток верхней строки и левого столбца, Робот может попасть либо из клетки слева, либо из клетки сверху.
Сначала найдём максимальную сумму бонусов. Для этого найдём максимальную сумму для каждой клетки таблицы.
Для каждой клетки верхней строки существует только один способ попасть в неё: двигаться всё время вправо. Поэтому значение для такой клетки равно сумме всех клеток слева от неё вместе с текущей клеткой.
Для каждой клетки левого столбца существует только один способ попасть в неё: двигаться всё время вниз. Поэтому значение равно сумме всех клеток выше неё вместе с текущей клеткой.
Расчётную таблицу разместим справа от исходной, начиная с ячейки Q1.
В ячейку Q1 запишем формулу: =СУММ($A$1:A1)
Скопируем эту формулу во все ячейки диапазона R1:AE1 и диапазона Q2:Q15.
Для остальных клеток будем сравнивать значение ячейки слева и значение ячейки сверху. Выбираем большее из них и прибавляем значение соответствующей клетки исходной таблицы.
В ячейку R2 запишем формулу: =ЕСЛИ(Q2>R1;Q2+B2;R1+B2)
Скопируем эту формулу во все ячейки диапазона R2:AE15. Например, для первых клеток получаем:
$Q1=27$,
$R1=27+13=40$,
$Q2=27+24=51$,
$R2=30+\max(40;51)=81$.
Таким образом, в ячейке AE15 получим значение максимальной суммы бонусов: $710$.
Аналогичным образом найдём минимальную сумму бонусов.
Ячейки диапазонов Q1:Q15 и R1:AE1 заполняются так же, как при поиске максимальной суммы.
Для остальных клеток теперь нужно выбирать меньшее из значений слева и сверху.
В ячейку R2 запишем формулу: =ЕСЛИ(Q2<R1;Q2+B2;R1+B2)
Скопируем эту формулу во все ячейки диапазона R2:AE15. Например, $R2=30+\min(40;51)=70$.
Таким образом, в ячейке AE15 получим значение минимальной суммы бонусов: $485$.
По условию сначала записывается минимальная сумма, затем максимальная: $485\ 710$.
Код на Python
Если сохранить исходную таблицу в формате CSV с именем 18-01.csv, решение можно записать так:
s = tuple(
tuple(int(x) for x in row.split(';'))
for row in open('18-01.csv').read().splitlines()
)
N = len(s)
ans = []
for f in [min, max]:
m = [[0 for _ in range(N)] for _ in range(N)]
m[0][0] = s[0][0]
for i in range(1, N):
m[0][i] = s[0][i] + m[0][i - 1]
m[i][0] = s[i][0] + m[i - 1][0]
for row in range(1, N):
for column in range(1, N):
m[row][column] = (
s[row][column]
+ f(m[row - 1][column], m[row][column - 1])
)
ans.append(m[N - 1][N - 1])
print(*ans)
Программа выводит:
485 710