Квадрат разлинован на N×N клеток
Откройте файл. Определите максимальную и минимальную денежную сумму, которую может собрать Робот, пройдя из левой верхней клетки в правую нижнюю. В ответ запишите два числа друг за другом без разделительных знаков — сначала максимальную сумму, затем минимальную.
Исходные данные представляют собой электронную таблицу размером N×N, каждая ячейка которой соответствует клетке квадрата.
Пример входных данных:
| 1 | 8 | 8 | 4 |
| 10 | 1 | 1 | 3 |
| 1 | 3 | 12 | 2 |
| 2 | 3 | 5 | 6 |
Для указанных входных данных ответом должна быть пара
Сначала найдём максимальную денежную сумму. Для этого найдём максимальную денежную сумму для каждой ячейки таблицы. Для каждой ячейки верхней строки это будет сумма всех ячеек слева от текущей. Для каждой ячейки левого столбца это будет сумма всех ячеек сверху от текущей.
Аналогичным образом найдём значение минимальной денежной суммы. Ячейки диапазонов L1:L10 и M1:U1 заполняются также, как при поиске максимальной денежной суммы.
Ответ: 1204502.
Приведём решение Артёма Гридина на языке Python.
s = tuple(tuple(int(x) for x in m.split(';')) for m in open('18_demo.csv').read().splitlines())
N = len(s)
for f in [lambda a, b: max(a, b), lambda a,b: min(a, b)]:
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])
print(m[N-1][N-1],end='')