Задание 18 ЕГЭ по информатике · 01C951

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

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

1. Начальную клетку включают в сумму бонусов. Для неё минимальная и максимальная суммы равны её бонусу.
min[1][1]=max[1][1]=bonus[1][1]

2. Для каждой следующей клетки рассматривают только разрешённые переходы из клетки сверху и из клетки слева.
min[i][j]=bonus[i][j]+min(допустимые min[i−1][j], min[i][j−1])

3. Аналогично находят максимальную сумму.
max[i][j]=bonus[i][j]+max(допустимые max[i−1][j], max[i][j−1])

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