18. Исполнитель Робот: Условие
Условие
Квадрат разлинован на $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=18$,
$R1=18+44=62$,
$Q2=18+12=30$,
$R2=36+\max(62;30)=98$.
В ячейке AE15 получим максимальную сумму: $1043$.
Для поиска минимальной суммы заменим сравнение в R2:
=ЕСЛИ(Q2<R1;Q2+B2;R1+B2)
После копирования формулы в диапазон R2:AE15 получим: $645$.
Код на Python
Сохраним исходную таблицу в формате CSV под именем 18-04.csv.
s = tuple(
tuple(map(int, row.split(';')))
for row in open('18-04.csv').read().splitlines()
)
N = len(s)
mn = [[0] * N for _ in range(N)]
mx = [[0] * N for _ in range(N)]
mn[0][0] = mx[0][0] = s[0][0]
for j in range(1, N):
mn[0][j] = mx[0][j] = mx[0][j - 1] + s[0][j]
for i in range(1, N):
mn[i][0] = mx[i][0] = mx[i - 1][0] + s[i][0]
for i in range(1, N):
for j in range(1, N):
mn[i][j] = s[i][j] + min(mn[i - 1][j], mn[i][j - 1])
mx[i][j] = s[i][j] + max(mx[i - 1][j], mx[i][j - 1])
print(mn[-1][-1], mx[-1][-1])
Программа выводит:
645 1043