Задание выполняется с использованием прилагаемых файлов.
Робот стоит в влевом нижнем углу прямоугольного поля, в каждой клетке которого записано целое число (-1 или натуральное число).
В некоторых клетках записано число –1, в эти клетки роботу заходить нельзя.
Для вашего удобства такие клетки выделены зелёным фоном. В остальных клетках записаны положительные числа.
За один ход робот может переместиться на одну клетку вправо или на одну клетку вверх.
Клетка, из которой робот не может сделать допустимого хода (слева и снизу находятся границы поля или запрещённые клетки),
называется финальной. На поле может быть несколько финальных клеток.
Гарантируется, что робот может добраться до всех клеток с натуральными значениями
В начальный момент робот обладает некоторым запасом энергии.
- Расход энергии на запуск робота равен числу, записанному в стартовой клетке.
- В дальнейшем расход энергии на переход в каждую следующую клетку равен числу, записанному в этой клетке.
Выполните следующие задания:
- Определите количество финальных клеток в таблице
- Определите минимальный начальный запас энергии, который позволит роботу добраться до любой из финальных клеток.
- Определите минимальный начальный запас энергии, который позволит роботу пройти любым допустимым маршрутом.
Входные данные:
Исходная таблица в форматах .txt, .xls, .xlsx
Выходные данные:
Ответы на задания (три числа в трех строках)