Задание 18 ЕГЭ по информатике: максимум и минимум на пути в таблице

Робот собирает числа на маршруте по таблице. Найдите лучший и худший путь и проверьте обе суммы.

Следующая задача в кабинете

Проверьте ответ здесь. Появится кнопка к другим заданиям этого номера.

К упражнениям
Скачать 18-grid.txt

В файле 15 строк по 15 чисел. Пробелы отделяют столбцы.

В таблице 6 8 / 2 5 пути дают 19 и 13. Ответ записывается как 19 13.

Задания

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])

Дальше по теме

Источники