Задание 18 ЕГЭ по информатике: робот на клеточном поле — разбор и примеры

В задании 18 дан файл электронной таблицы с квадратным полем, например 10 × 10 или 15 × 15 клеток. В каждой клетке лежит монета определённого достоинства. Робот стартует в левой верхней клетке и за каждый ход сдвигается на одну клетку вправо или вниз, пока не придёт в правую нижнюю клетку; на некоторых границах между клетками стоят стены, через которые проходить нельзя. Нужно найти максимальную и минимальную сумму монет, которую может собрать робот. Перебирать все маршруты невозможно — их слишком много, но задача элегантно решается динамическим программированием.

Что проверяет задание

• понимание идеи динамического программирования: ответ для клетки строится из ответов для соседних клеток;
• умение писать формулы с относительными ссылками в электронной таблице и протягивать их;
• аккуратность в обработке стен и границ поля;
• умение вычислить и максимум, и минимум, не перепутав их.

Идея решения

Обозначим через S(i, j) наибольшую сумму, которую робот может собрать по пути от старта до клетки (i, j), включая монету в ней самой. В клетку (i, j) робот попадает либо сверху, из (i − 1, j), либо слева, из (i, j − 1). Значит:

S(i, j) = монета(i, j) + наибольшее из S(i − 1, j) и S(i, j − 1).

Для первой строки возможен только приход слева, для первого столбца — только сверху. Если между клетками стоит стена, соответствующий вариант просто исключается. Для минимальной суммы формула та же, только с функцией МИН вместо МАКС.

Типичные формулировки

1. «Определите максимальную и минимальную денежную сумму, которую может собрать робот. В ответе укажите два числа: сначала максимальную, затем минимальную».
2. Робот ходит вправо или вверх из левой нижней клетки — меняется направление заполнения таблицы.
3. Робот ходит вправо, вниз или по диагонали — в формуле появляется третий сосед.
4. Стены обозначены утолщёнными линиями на границах клеток — их нужно найти глазами в таблице.

Пошаговый метод в электронной таблице

1. Скопируйте поле справа или ниже исходного — это будет таблица сумм. Пусть поле занимает A1:J10, таблица сумм — L1:U10.
2. Стартовая клетка: в L1 запишите =A1.
3. Первая строка: в M1 запишите =L1+B1 и протяните вправо.
4. Первый столбец: в L2 запишите =L1+A2 и протяните вниз.
5. Остальные клетки: в M2 запишите =МАКС(L2;M1)+B2 и протяните на всю таблицу.
6. Стены: в клетках, куда нельзя прийти слева (стена слева), замените формулу на =M1+B2 (только сверху); куда нельзя прийти сверху — на вариант только слева. Если стен много, удобно сначала протянуть общую формулу, а потом вручную исправить клетки у стен.
7. Ответ — значение в правой нижней клетке таблицы сумм. Затем скопируйте таблицу и замените МАКС на МИН.

Разбор примера

Поле 5 × 5 (номер строки — слева, номер столбца — сверху):

Робот ходит вправо или вниз из клетки (1, 1) в клетку (5, 5). Заполним таблицу наибольших сумм по формуле:

Например, S(2, 2) = 8 + наибольшее из 10 и 11 = 19, а S(3, 3) = 7 + наибольшее из 20 и 25 = 32. Максимальная сумма — 56. Восстановим маршрут, идя от конца к началу в сторону большего соседа: 7 → 4 → 8 → 6 → 7 → 9 → 3 → 8 → 4 (вниз, вправо, вниз, вправо, вправо, вниз, вправо, вниз). Сумма 7 + 4 + 8 + 6 + 7 + 9 + 3 + 8 + 4 = 56.

Таблица наименьших сумм строится так же с МИН; в правом нижнем углу получается 36. Ответ: 56 36.

Вариант со стеной. Пусть между клетками (3, 2) и (3, 3) стоит стена, то есть из (3, 2) нельзя сделать ход вправо. Тогда S(3, 3) = 7 + 20 = 27 (только сверху), и найденный выше маршрут становится невозможным. Пересчитав таблицу, получаем максимум 51, а минимум не меняется — 36, потому что минимальный маршрут через эту стену не проходил.

Код на Python

Если поле сохранить как CSV или скопировать в программу, ответ проверяется за секунду. Стены удобно задавать множеством клеток, из которых нельзя идти вправо (и отдельно — вниз).

g = [[7, 3, 9, 2, 6],
     [4, 8, 1, 5, 3],
     [2, 6, 7, 9, 1],
     [9, 1, 4, 3, 8],
     [5, 7, 2, 6, 4]]
n = len(g)

def solve(best, no_right=frozenset()):
    d = [[0] * n for _ in range(n)]
    for i in range(n):
        for j in range(n):
            options = []
            if i > 0:
                options.append(d[i - 1][j])
            if j > 0 and (i, j - 1) not in no_right:
                options.append(d[i][j - 1])
            d[i][j] = g[i][j] + (best(options) if options else 0)
    return d[n - 1][n - 1]

print(solve(max), solve(min))                    # 56 36
wall = {(2, 1)}   # строка 3, столбец 2 (нумерация с нуля)
print(solve(max, wall), solve(min, wall))        # 51 36

Частые ошибки

• Протягивают общую формулу через стены и забывают её исправить — максимум получается завышенным.
• Путают направление: если робот идёт вправо и вверх, таблицу нужно заполнять снизу вверх.
• Неверно заполняют первую строку и первый столбец: там нет выбора, только накопленная сумма.
• Копируют таблицу МАКС для МИН и забывают заменить функцию во всех клетках.
• Не включают монету стартовой клетки или финишной — по условию обычно учитываются обе.
• Путают порядок в ответе: сначала максимальная сумма, потом минимальная.

Потренируйтесь

Решите несколько полей разного размера, со стенами и без: задания № 18 в банке. Подробнее о методе — в статьях «Подсчёт путей и динамическое программирование» и «Электронные таблицы: формулы и рабочие шаблоны». Следующая тема — задание 19: теория игр.