В задании 18 ЕГЭ по информатике нам дано квадратное поле, по которому перемещается виртуальный робот-сборщик монет. Поле представлено электронной таблицей, а число в каждой ячейке показывает стоимость лежащей там монеты.
На перемещения робота накладываются ограничения. В зависимости от условия он может двигаться, например, вправо и вниз или вправо и вверх. Толстые границы ячеек обозначают стены, сквозь которые пройти нельзя.
В тренировочных заданиях иногда встречаются дополнительные правила, например телепортация. Здесь разберём основной тип со стенами: именно на нём проще всего понять общий алгоритм.
Нужно подсчитать сумму монет на пути из начальной клетки в одну из конечных. Конечная клетка — та, из которой робот не может выполнить ни одну разрешённую команду из-за стен или границы поля.
Обычно в ответ нужно записать максимальную и минимальную итоговые суммы. Но их порядок всегда проверяйте по условию: иногда сначала требуется минимум. По сути, мы ищем оптимальный путь в матрице с помощью динамического программирования.
Динамическое программирование
Представьте ситуацию: вы пишете программу для навигатора, который должен найти самый быстрый маршрут из точки А в точку Б в большом городе.
Или создаёте игру, где персонаж должен собрать максимум золота, перемещаясь по подземелью.
Или решаете задание ЕГЭ по информатике, где робот собирает монеты на поле из множества клеток.
Что общего у всех этих задач? Нужно найти оптимальный путь среди множества возможных вариантов. И здесь начинаются проблемы.
Давайте возьмём простой пример: поле 3×3, где в каждой клетке лежит какое-то количество монет. Робот начинает путь в левом верхнем углу и должен дойти до правого нижнего, двигаясь только вправо или вниз. Нужно собрать максимум монет.
Первая мысль: «Давайте просто переберём все возможные пути».
И так далее… Всего для поля 3×3 существует 6 различных путей. Ну ничего, можно перебрать.
А теперь задумайтесь: сколько путей на поле 4×4? Уже 20. На поле 5×5 — 70. А на условном поле 30×30 количество путей превышает 30 квадриллионов!
Откуда берётся это число? Чтобы попасть из одного угла поля 30×30 в другой, робот делает 29 шагов вправо и 29 вниз — всего 58 шагов.
Разные пути отличаются только порядком этих шагов. Нужно выбрать, какие 29 позиций из 58 займут движения вправо: C(58, 29) ≈ 30 квадриллионов.
Перебрать такое количество вариантов вручную невозможно, да и прямой перебор на компьютере займёт неприемлемо много времени. На экзамене этот подход точно не подойдёт.
Но ту же задачу можно решить, обработав всего 900 клеток. Вместо десятков квадриллионов путей мы один раз вычислим лучший результат для каждой клетки.
Секрет кроется в динамическом программировании. Вместо построения всех маршрутов мы сохраняем в каждой клетке одно число — лучший результат, с которым робот может до неё добраться.
Сравните:
Перебор всех путей на поле 30×30: больше 30 000 000 000 000 000 вариантов
Динамическое программирование на том же поле: 900 клеток
Разница огромна: вместо полного перебора мы последовательно заполняем небольшую таблицу. Именно поэтому динамическое программирование подходит для задания 18.
Динамическое программирование — это метод, при котором большая задача разбивается на связанные подзадачи, а уже найденные результаты сохраняются и используются дальше.
Звучит довольно сложно, не так ли? На самом деле принцип очень простой. Представьте, что вы едете из своего города в другой город на машине, и по дороге в каждом населённом пункте можете заправиться.
На разных заправках разные цены, и вам нужно потратить минимум денег на бензин. Из каждого города можно поехать в несколько разных направлений – есть множество маршрутов.
Глупый подход: для каждого возможного маршрута (а их могут быть тысячи!) пересчитывать всю стоимость бензина от начала до конца.
Умный подход: для каждого города записать одно число — минимальную стоимость пути до него. При переходе в следующий город смотрим на уже посчитанные соседние результаты и выбираем самый выгодный.
Вот и весь фокус динамического программирования: запоминать промежуточные результаты, чтобы не пересчитывать одно и то же много раз.
Для нашей задачи достаточно запомнить три идеи:
Результат для текущей клетки зависит от результатов в клетках, из которых робот может в неё прийти.
Одни и те же промежуточные клетки входят во множество разных маршрутов.
Поэтому каждую клетку выгоднее посчитать один раз и сохранить результат в накопительной таблице.
В задании 18 подзадача — это вопрос: «Какую лучшую сумму можно набрать к конкретной клетке?» Когда ответы для соседей уже известны, текущая клетка считается одним действием.
Использование методов динамического программирования
Но давайте вернёмся к нашему примеру поля 3×3 и попробуем решить поставленную задачу, но уже не простым перебором, а с помощью динамического программирования.
Нам не нужно строить все пути. Для каждой клетки задаём обратный вопрос: «Из каких соседних клеток робот мог прийти сюда и какой из этих путей выгоднее?»
Если робот двигается вправо и вниз, в обычную клетку он может прийти только слева или сверху. А в клетки первой строки и первого столбца ведёт лишь один допустимый путь.
По первому столбцу можно двигаться только вниз.
По первой строке можно двигаться только вправо.
Поэтому границы таблицы заполняются простым накоплением: к предыдущей сумме прибавляем значение новой клетки. Выбирать между двумя маршрутами там не приходится.
Составим вторую, накопительную таблицу. В каждой её клетке будет храниться не отдельная монета, а лучшая сумма, которую робот может собрать к этому моменту.
Например, в правой клетке первой строки получится 4: 1 + 5 − 2. В нижней клетке первого столбца получится 2: 1 − 1 + 2. Здесь путь единственный, поэтому сравнивать варианты не нужно.
В центральную клетку уже можно прийти двумя способами: сверху, где накоплено 6, или слева, где накоплено 0.
Для максимальной суммы выбираем большего предшественника: 6. Прибавляем значение текущей клетки −3 и получаем 3. Если бы пришли слева, получилось бы 0 − 3 = −3.
В правую клетку второй строки выгоднее прийти сверху, где накоплено 4: 4 + 1 = 5.
В среднюю клетку третьей строки выгоднее прийти сверху, где накоплено 3: 3 + 3 = 6.
В последнюю клетку выгоднее прийти слева, где накоплено 6: 6 + 2 = 8.
В итоге максимальная сумма на пути из левой верхней клетки в правую нижнюю равна 8.
Сделаем вывод. В каждой «развилке» для максимума выбираем большую из накопленных сумм сверху и слева, а затем прибавляем значение текущей клетки.
На первой строке и в первом столбце предшественник только один, поэтому там функция МАКС() не нужна.
Запишем эту логику формально. Исходную таблицу назовём A, а накопительную — B.
Робот пришёл в текущую клетку либо сверху, либо слева — третьего варианта при командах «вправо» и «вниз» нет.
Всю историю пути пересчитывать не нужно. В соседних клетках уже лежат лучшие суммы до них. Поэтому сравниваем только эти два готовых результата.
Для максимального пути берём больший результат, для минимального — меньший. После выбора прибавляем монету из текущей клетки.
Например, сверху накоплено 80, слева — 71, а в клетке лежит 12. Максимум равен 80 + 12 = 92, минимум — 71 + 12 = 83.
В начальной клетке робот сразу забирает монету, поэтому:
B[0][0] = A[0][0]
Для внутренней клетки в строке i и столбце j формула максимума выглядит так:
B[i][j] = max(B[i−1][j], B[i][j−1]) + A[i][j]
B[i−1][j] — сумма сверху, B[i][j−1] — сумма слева, а A[i][j] — монета в текущей клетке. Сначала выбираем лучший вход, затем прибавляем новую монету.
Если вход сверху или слева перекрыт стеной, соответствующего предшественника использовать нельзя. Тогда оставляем только разрешённый путь. Если закрыты оба входа, клетка недостижима и должна остаться пустой.
Стена меняет не арифметику, а список допустимых предшественников. МАКС() или МИН() можно применять только к тем соседям, из которых робот действительно способен войти.
Для первой строки, где можно прийти только слева, получаем:
B[0][j] = B[0][j−1] + A[0][j]
В нашей задаче это выглядит так:
B[0][1] = B[0][0] + A[0][1] = 1 + 5 = 6
Для крайнего левого столбца, где можно прийти только сверху, формула будет такой:
B[i][0] = B[i−1][0] + A[i][0]
Если требуется минимальная сумма, логика не меняется. В развилке вместо максимального предшественника выбираем минимального: функцию МАКС() заменяем на МИН().
Как восстановить формулу на экзамене
Если формула забылась, нарисуйте стрелки разрешённых движений и разверните их назад от текущей клетки.
При движении вправо и вниз стрелки назад указывают влево и вверх. Значит, предшественники находятся слева и сверху.
Зачеркните направления, перекрытые стенами, и недостижимые клетки. Из оставшихся сумм выберите МАКС() или МИН(), затем прибавьте значение текущей клетки.
Эта схема работает и для других направлений. Например, при движении вправо и вверх предшественники находятся слева и снизу.
Алгоритм решения
Составим алгоритм решения задания 18 для движения вправо и вниз:
Ниже исходного поля создаём накопительную таблицу такого же размера.
Переносим значение начальной клетки. Первую строку и первый столбец заполняем прибавлением текущей монеты к единственной предыдущей сумме.
Для внутренних клеток используем формулу: МАКС(сумма слева; сумма сверху) + значение текущей клетки.
Восстанавливаем толстые границы исходного поля, чтобы видеть стены и не использовать запрещённые переходы.
Отмечаем конечные клетки. При движении вправо и вниз у них закрыты выходы справа и снизу.
Удаляем результаты из недостижимых клеток: в них нельзя попасть ни из одного разрешённого предшественника.
Исправляем формулы возле стен. Если вход сверху закрыт, оставляем путь слева. Если закрыт вход слева — путь сверху.
Среди конечных клеток выбираем максимальную накопленную сумму и записываем её отдельно.
В накопительной таблице заменяем МАКС() на МИН(), не затрагивая исходные данные.
Среди конечных клеток выбираем минимальную сумму и записываем ответы в порядке, указанном в условии.
Не ищите максимум или минимум по всей таблице. Робот может закончить маршрут только в конечной клетке, поэтому сравнивать нужно исключительно отмеченные конечные точки.
После замены МАКС() на МИН() ещё раз проверьте формулы возле стен: в них функции выбора уже нет, и они не должны измениться.
Теперь рассмотрим работу этого алгоритма на конкретных примерах.
Квадрат разлинован на N × N клеток (1 < N < 30).
Исполнитель Робот может перемещаться по клеткам, выполняя за одно перемещение одну из двух команд: вправо или вниз. По команде вправо Робот перемещается в соседнюю правую клетку, по команде вниз – в соседнюю нижнюю.
Квадрат ограничен внешними стенами. Между соседними клетками квадрата также могут быть внутренние стены. Сквозь стену Робот пройти не может.
Перед каждым запуском Робота в каждой клетке квадрата лежит монета достоинством от 1 до 100. Посетив клетку, Робот забирает монету с собой; это также относится к начальной и конечной клеткам маршрута Робота.
В «угловых» клетках поля – тех, которые справа и снизу ограничены стенами, Робот не может продолжать движение, поэтому накопленная сумма считается итоговой. Таких конечных клеток на поле может быть несколько, включая правую нижнюю клетку поля. При разных запусках итоговые накопленные суммы могут различаться.
Определите максимальную и минимальную денежные суммы среди всех возможных итоговых сумм, которые может собрать Робот, пройдя из левой верхней клетки в конечную клетку маршрута.
В ответе укажите два числа – сначала максимальную сумму, затем минимальную.
Исходные данные представляют собой электронную таблицу размером N × N, каждая ячейка которой соответствует клетке квадрата. Внутренние и внешние стены обозначены утолщёнными линиями.
Откроем приложенный файл. Исходное поле занимает диапазон A1:T20.
Выделяем таблицу и копируем её ниже. Начало новой таблицы — A22. Удаляем из копии числа, но оставляемзначение начальной клетки A22.
Заполняем первую строку накопительной таблицы. В B22 пишем =A22+B1 и растягиваем формулу до T22. Здесь A22 — предыдущая сумма, а B1 — новая монета.
Аналогично заполняем первый столбец. В A23 пишем =A22+A2 и растягиваем формулу до A41.
Теперь заполним внутренние клетки. Для B23 доступные предшественники находятся слева, в A23, и сверху, в B22. Значение текущей монеты берём из B2.
=МАКС(A23;B22)+B2
Читаем формулу словами: «Выбрать большую сумму слева и сверху, затем прибавить монету из B2».
Растягиваем формулу вправо и вниз. Пока стены не учтены, это только заготовка накопительной таблицы.
При растягивании формулы оформление ячеек может перекрыть толстые границы. Вернём их из исходной таблицы инструментом «Копировать формат».
Выделяем диапазон A22:T41 и применяем скопированный формат. Теперь стены снова видны поверх накопительной таблицы.
Зелёным отметим конечные клетки — те, у которых закрыты выходы справа и снизу. В этой задаче таких клеток четыре.
Ответ пока выбирать рано: обычная формула не знает о стенах. Нужно исправить клетки, в которые нельзя войти сверху или слева.
Оранжевым (хотя тут скорее коралловым цветом) отметим клетки под горизонтальными стенами: вход сверху для них закрыт.
Синим отметим клетки справа от вертикальных стен: вход слева для них закрыт.
В диапазон M31:N36 робот не может попасть ни сверху, ни слева. Эти клетки недостижимы, поэтому выделим их красным и удалим из них формулы.
Начнём с оранжевых/коралловых клеток. Путь сверху перекрыт, поэтому оставляем сумму слева и значение текущей клетки. Можно скопировать подходящую формулу из 22-й строки.
В синих клетках вход слева перекрыт. Оставляем только сумму сверху и значение текущей клетки.
Удобная памятка: клетка под стеной не видит верхнего соседа, а клетка справа от стены — левого. Если закрыты оба допустимых входа, формулу удаляем полностью.
Среди конечных клеток максимальная сумма равна 2362 — она находится в S39. Это первый ответ.
Записываем максимум отдельно, затем нажимаемCtrl+H. В поле «Найти» вводим «МАКС», а в поле «Заменить на» — «МИН». Замену выполняем только в формулах накопительной таблицы.
После пересчёта находим минимальное значение среди конечных клеток. Оно равно 1205 и находится в O41.
Ответ: 2362 1205.
Пример 1
Для закрепления решим ещё одно задание с такой же формулировкой.
Квадрат разлинован на N × N клеток (1 < N < 30).
Исполнитель Робот может перемещаться по клеткам, выполняя за одно перемещение одну из двух команд: вправо или вниз. По команде вправо Робот перемещается в соседнюю правую клетку, по команде вниз – в соседнюю нижнюю.
Квадрат ограничен внешними стенами. Между соседними клетками квадрата также могут быть внутренние стены. Сквозь стену Робот пройти не может.
Перед каждым запуском Робота в каждой клетке квадрата лежит монета достоинством от 1 до 100. Посетив клетку, Робот забирает монету с собой; это также относится к начальной и конечной клеткам маршрута Робота.
В «угловых» клетках поля – тех, которые справа и снизу ограничены стенами, Робот не может продолжать движение, поэтому накопленная сумма считается итоговой. Таких конечных клеток на поле может быть несколько, включая правую нижнюю клетку поля. При разных запусках итоговые накопленные суммы могут различаться.
Определите максимальную и минимальную денежные суммы среди всех возможных итоговых сумм, которые может собрать Робот, пройдя из левой верхней клетки в конечную клетку маршрута.
В ответе укажите два числа – сначала максимальную сумму, затем минимальную.
Исходные данные представляют собой электронную таблицу размером N × N, каждая ячейка которой соответствует клетке квадрата. Внутренние и внешние стены обозначены утолщёнными линиями.
Алгоритм здесь тот же, поэтому сосредоточимся на стенах, недостижимых клетках и конечных точках.
Открываем приложенный к заданию файл.
Копируем поле ниже и заполняем накопительную таблицу.
Отмечаем клетки под горизонтальными стенами и справа от вертикальных, конечные точки и недостижимые области.
Исправляем формулы возле стен и ищем максимум только среди конечных клеток.
Максимум находится в T41 и равен 2132.
Сохраняем это число, заменяем в накопительной таблице МАКС() на МИН() и снова проверяем только конечные клетки.
Минимальная итоговая сумма равна 663.
Ответ: 2132663.
Пример 2
Теперь рассмотрим задание, в котором робот двигается вправо и вверх.
Алгоритм остаётся прежним, но старт переносится в левый нижний угол, а формулы «отзеркаливаются» по вертикали.
Формулировка будет такая:
Квадрат разлинован на N × N клеток (1 < N < 30).
Исполнитель Робот может перемещаться по клеткам, выполняя за одно перемещение одну из двух команд: вправо или вверх. По команде вправо Робот перемещается в соседнюю правую клетку, по команде вверх – в соседнюю верхнюю.
Квадрат ограничен внешними стенами. Между соседними клетками квадрата также могут быть внутренние стены. Сквозь стену Робот пройти не может.
Перед каждым запуском Робота в каждой клетке квадрата лежит монета достоинством от 1 до 100. Посетив клетку, Робот забирает монету с собой; это также относится к начальной и конечной клеткам маршрута Робота.
В «угловых» клетках поля – тех, которые справа и сверху ограничены стенами, Робот не может продолжать движение, поэтому накопленная сумма считается итоговой. Таких конечных клеток на поле может быть несколько, включая правую верхнюю клетку поля. При разных запусках итоговые накопленные суммы могут различаться.
Определите максимальную и минимальную денежные суммы среди всех возможных итоговых сумм, которые может собрать Робот, пройдя из левой нижней клетки в конечную клетку маршрута.
В ответе укажите два числа – сначала минимальную сумму, затем максимальную.
Исходные данные представляют собой электронную таблицу размером N × N, каждая ячейка которой соответствует клетке квадрата. Внутренние и внешние стены обозначены утолщёнными линиями.
Как обычно, открываем прикреплённый файл с электронной таблицей.
Копируем поле ниже, но теперь сохраняем левую нижнюю начальную клетку A41.
По левому столбцу робот идёт вверх, поэтому для A40 берём сумму из нижней клетки A41 и прибавляем монету из A19: =A41+A19.
По нижней строке робот идёт вправо. Для B41 берём сумму слева A41 и монету из B20: =A41+B20.
Для внутренней клетки правило будет таким: МАКС(сумма слева; сумма снизу) + текущая монета. Для минимума используем тех же предшественников, но функцию МИН().
Внутренние клетки теперь получают предшественников слева и снизу. Заполняем таблицу и восстанавливаем формат исходного поля.
Отмечаем конечные клетки, стены слева и снизу, а также недостижимую область J38:T41.
Исправляем формулы возле стен. Затем среди конечных клеток находим максимальное значение.
Максимальная итоговая сумма равна 2828.
Заменяем МАКС() на МИН() и находим минимальную итоговую сумму — 743.
В условии требуется сначала минимум, затем максимум. Поэтому ответ: 743 2828.
Итоги
В задании 18 таблица заполняется от начальной клетки по направлению движения робота. Для каждой клетки мы смотрим, из каких уже посчитанных клеток робот мог прийти, исключаем пути через стены и прибавляем текущую монету.
При поиске максимума выбираем МАКС(), при поиске минимума — МИН(). Формулу не нужно заучивать целиком: направления прихода всегда противоположны разрешённым командам робота, поэтому её можно восстановить прямо на экзамене.
В конце сравниваем только допустимые конечные клетки и записываем результаты в порядке из условия. Так один и тот же алгоритм работает при любом наборе разрешённых направлений.
На этом мы закончили разбор задания 18 ЕГЭ по информатике. Попрактиковаться можно в нашем тренажёре.
Разберём эту тему на бесплатном пробном занятии
Преподаватель покажет, как решать такие задачи, и подскажет, с чего начать подготовку. Группы до 8 человек, очно в Калининграде и онлайн.
Мы используем файлы cookie. Необходимые обеспечивают работу сайта: корзину и вход в личный кабинет. С вашего согласия мы также используем сервис Яндекс Метрика, чтобы анализировать посещаемость и улучшать сайт.
Подробнее — в политике конфиденциальности.
