1Авторская задача
Таблица 15 на 15. Робот стартует в левом верхнем углу и завершается в правом нижнем. Он ходит только вправо или вниз на одну клетку и собирает числа всех посещённых клеток, включая начало и конец. Найдите максимальную и минимальную суммы. Укажите максимум первым.
Решение
Для каждой клетки считаем две величины. В них входят число клетки и соответствующий экстремум из доступных предшественников сверху и слева. Стартовую клетку инициализируем её собственным значением.
from pathlib import Path
a = [list(map(int, row.split())) for row in Path("18-grid.txt").read_text().splitlines()]
n, m = len(a), len(a[0])
lo = [[0] * m for _ in a]
hi = [[0] * m for _ in a]
for i in range(n):
for j in range(m):
if i == j == 0:
lo[i][j] = hi[i][j] = a[i][j]
continue
prev = [(y, x) for y, x in ((i - 1, j), (i, j - 1)) if y >= 0 and x >= 0]
lo[i][j] = a[i][j] + min(lo[y][x] for y, x in prev)
hi[i][j] = a[i][j] + max(hi[y][x] for y, x in prev)
print(hi[-1][-1], lo[-1][-1])