18_0371

Задание выполняется с использованием прилагаемого файла.

Квадрат разлинован на $16\times16$ клеток. Исполнитель Робот может перемещаться по клеткам, выполняя за одно перемещение одну из двух команд: вправо или вниз. По команде вправо Робот перемещается в соседнюю правую клетку, по команде вниз — в соседнюю нижнюю.

Квадрат ограничен внешними стенами. Между соседними клетками также могут быть внутренние стены. Сквозь стену Робот пройти не может.

Каждая клетка окрашена в зелёный или красный цвет и содержит монету достоинством от 1 до 100. Посетив клетку, Робот забирает монету, включая монеты в начальной и конечной клетках маршрута.

Робот начинает движение в левой верхней клетке. Маршрут заканчивается в клетке, которая справа и снизу ограничена стенами. Таких конечных клеток может быть несколько.

Результатом маршрута считается сумма монет, собранных в зелёных клетках, минус сумма монет, собранных в красных клетках. Результат может быть отрицательным.

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

Исходные данные представлены электронной таблицей, каждая ячейка которой соответствует клетке поля. Внутренние и внешние стены обозначены утолщёнными линиями. Цвет каждой ячейки соответствует цвету клетки поля.

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

• 18_0371.ods