ЕГЭОГЭ
18

Минимальный и максимальный путь

ЕГЭ · Информатика · Задание 18 · Динамическое программирование
ВысокаяФИПИD99C0CКороткий ответ≈ 10 минут

Квадрат разлинован на $N \times N$ клеток ($1 < N < 26$). В каждой клетке указан натуральный бонус, не превышающий 100. Робот перемещается из левой верхней клетки в правую нижнюю, выполняя команды «вправо» или «вниз». Через границы клеток, отмеченные в электронной таблице утолщением, проходить нельзя. При посещении клетки Робот забирает указанный в ней бонус, включая начальную и конечную клетки.

Файл к заданию

Определите минимальную и максимальную суммы бонусов, которые может собрать Робот. Исходные данные представлены в электронной таблице размером $N \times N$.

Условие как в банке ФИПИ — открыть и сверить
Впишите правильный ответ.

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

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

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

Исходные данные представлены в форме электронной таблицы размером
N × N, в которой одна ячейка соответствует одной клетке квадрата. Стены, через которые Роботу нельзя проходить, отмечены в электронной таблице границами с утолщением.

Пример входных данных:

1

8

8

4

10

1

1

3

1

3

12

2

2

3

5

6

Для указанных входных данных ответом является пара чисел:

27

41

Ответ:



Ваш ответ

Формат: число или слово без единиц измерения; дробную часть отделяйте запятой.

Не выходит — подсказку
!
3 уровня: от лёгкого толчка до почти готового решения. Следующий открывается, когда прочитан предыдущий, — чтобы не перепрыгнуть сразу к ответу.
1Мягкая — с чего смотретьуровень 1 из 3

Из каких клеток может прийти Робот в текущую клетку, если разрешены только движения вправо и вниз?

2Наводящая — какие числа считатьуровень 2 из 3

Для каждой клетки храните две величины: минимальную и максимальную сумму бонусов на допустимом пути до неё. Переход выполняется только через границу без стены.

3Прямая — фактически решениеуровень 3 из 3

Для клетки $(i,j)$ прибавьте её бонус к минимуму или максимуму из доступных значений для клеток $(i-1,j)$ и $(i,j-1)$. В правой нижней клетке получатся искомые суммы.

Всё равно не складывается?Полное решение с обоснованием каждого шага — на отдельной странице.
Открыть решение

Задание 18 ЕГЭ, информатика

Задача из темы «Динамическое программирование»: в ней 72 задачи с ответом и разбором по шагам. В 18-м номере бланка — 49 задач.

Ответ можно проверить здесь же, а если не выходит — открыть подсказку или разбор. Регистрация не нужна.

Все задачи темы «Динамическое программирование»Решение этой задачи по шагамПравильный ответ к задачеВсе задачи задания 18 ЕГЭ по информатикеИнформатика: все задачи и темыПоиск по банку ЕГЭКонспект: Продвинутые алгоритмы и вычисления