Задание 18 ЕГЭ: робот со стенами: максимальная и минимальная сумма

Робот со стенами: путь в правый нижний угол. Тема номера — робот и динамическое программирование. Ниже — пример с ответом и решением; кнопкой под ним можно решить такую же задачу с другими числами, ответ проверится сразу.

Пример

Задание выполняется с использованием прилагаемого файла.

Квадрат разлинован на N × N клеток (1 < N < 30). Исполнитель Робот может перемещаться по клеткам, выполняя за одно перемещение одну из двух команд: вправо или вниз. По команде вправо Робот перемещается в соседнюю правую клетку, по команде вниз – в соседнюю нижнюю. Квадрат ограничен внешними стенами. Между соседними клетками квадрата также могут быть внутренние стены. Сквозь стену Робот пройти не может.

Перед каждым запуском Робота в каждой клетке квадрата лежит монета достоинством от 1 до 100. Посетив клетку, Робот забирает монету с собой; это также относится к начальной и конечной клеткам маршрута Робота.

Определите максимальную и минимальную денежные суммы, которые может собрать Робот, пройдя из левой верхней клетки в правую нижнюю. В ответе укажите два числа – сначала максимальную сумму, затем минимальную.

Исходные данные представляют собой электронную таблицу размером N × N, каждая ячейка которой соответствует клетке квадрата. Внутренние и внешние стены обозначены утолщёнными линиями (толстыми границами ячеек).

Типовой пример организации данных в файле

Типовой пример имеет иллюстративный характер. Для выполнения задания используйте данные из прилагаемого файла.

Запишите два числа через пробел.

Скачать файл к примеру

Решение

В клетку можно прийти только слева или сверху, поэтому считаем динамику: наибольшая сумма в клетке = монета в клетке + наибольшая из сумм у соседей слева и сверху, из которых сюда можно пройти (между ними нет стены). Для минимума — то же с наименьшей. Клетки, в которые нельзя попасть из левой верхней, не учитываются.

В электронной таблице: поле занимает A1:T20. Строим копию справа, начиная со столбца V: в V1 пишем =A1, в W1 — =V1+B1, в V2 — =V1+A2, а во внутренние клетки, например W2, — =B2+МАКС(V2;W1), и копируем формулы на всё поле. Там, где Робот упирается в стену, формулу правим вручную: за вертикальной стеной оставляем только соседа сверху, за горизонтальной — только соседа слева (недостижимые клетки очищаем). Для минимума делаем вторую копию с МИН. Стены удобно видеть прямо в файле — это толстые линии.

Ответ: 2499 1291.

Программа на Python читает числа и стены (стили границ ячеек) из файла с помощью openpyxl:

import openpyxl

ws = openpyxl.load_workbook("18.xlsx").active
n = ws.max_row
a = [[ws.cell(i + 1, j + 1).value for j in range(n)] for i in range(n)]


def thick(side):                     # стена — толстая граница ячейки
    return side is not None and side.style in ("medium", "thick")


def wall_right(i, j):                # стена справа от клетки (i, j), нумерация с 0
    return (j == n - 1 or thick(ws.cell(i + 1, j + 1).border.right)
            or thick(ws.cell(i + 1, j + 2).border.left))


def wall_down(i, j):                 # стена снизу от клетки (i, j)
    return (i == n - 1 or thick(ws.cell(i + 1, j + 1).border.bottom)
            or thick(ws.cell(i + 2, j + 1).border.top))


# mx, mn — наибольшая и наименьшая сумма на пути из левой верхней клетки; None — не дойти
mx = [[None] * n for _ in range(n)]
mn = [[None] * n for _ in range(n)]
for i in range(n):
    for j in range(n):
        prev = [(0, 0)] if i == j == 0 else []
        if j > 0 and mx[i][j - 1] is not None and not wall_right(i, j - 1):
            prev.append((mx[i][j - 1], mn[i][j - 1]))
        if i > 0 and mx[i - 1][j] is not None and not wall_down(i - 1, j):
            prev.append((mx[i - 1][j], mn[i - 1][j]))
        if prev:
            mx[i][j] = a[i][j] + max(t[0] for t in prev)
            mn[i][j] = a[i][j] + min(t[1] for t in prev)

print(mx[n - 1][n - 1], mn[n - 1][n - 1])

Решить такую задачу — новый вариант с проверкой