Задание 18. Информатика. Статград-22-3-2

Робот стоит в левом нижнем углу прямоугольного поля, в каждой клетке которого записано натуральное число. За один ход робот может переместится на одну клетку вправо или на одну клетку вверх. Выходить за пределы поля робот не может. Некоторые клетки на поле окружены границами, в эти клетки роботу заходить нельзя.

В начальный момент времен запас энергии робота составляет \( 3000 \) единиц. Проходя через каждую клетку робот расходует энергию, при этом расход равен числу, записанному в клетке. В клетках с выделенным фоном находятся зарядные станции. При прохождении через эти клетки робот не расходует а пополняет запас энергии. Сумма пополнения равна числу, записанному в этой клетке.

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

Исходные данные записаны в электронной таблице. Границы отмечены утолщенными линиями.

Пример входных данных (для таблицы размером \( 4 \times 4 \)):

13	8	69	50
30	35	57	17
32	90	55	32
44	12	80	43

При указанных входных данных максимальное значение получается при движении по маршруту \( 3000 - 44 - 12 + 90 - 55 - 32 - 17 - 50 = 2880\), а минимальное — при движении по маршруту \( 3000 - 44 - 12 - 80 - 55 - 32 - 17 - 50 = 2710 \).

Файл с данными

Исходная таблица с данными