Робот стоит в левом верхнем углу прямоугольного поля, в каждой клетке которого записано целое число.
В некоторых клетках записано число –1, в эти клетки роботу заходить нельзя. В остальных клетках записаны натуральные числа.
За один ход робот может переместиться на одну клетку вправо или на одну клетку вниз.
Клетка, из которой робот не может сделать допустимого хода (справа и снизу находятся границы поля или запрещённые клетки), называется финальной.
На поле может быть несколько финальных клеток.
В начальный момент робот обладает некоторым запасом энергии.
- Расход энергии на запуск робота равен числу, записанному в стартовой клетке.
- В дальнейшем расход энергии на переход в каждую следующую клетку равен числу, записанному в этой клетке.
Выполните следующие задания:
- Определите количество финальных клеток в таблице
- Определите минимальный начальный запас энергии, который позволит роботу добраться до какой-либо финальной клетки.
- Определите минимальный начальный запас энергии, который позволит роботу пройти любым допустимым маршрутом.
Входные данные.
Имя текстового файла с таблицей
Выходные данные
Ответы на задание (три числа в строке через пробел)
| входные данные (содержимое файла) |
выходные данные |
15 17 48 84 79 85 48 19 31 48
72 74 -1 44 48 -1 25 86 -1 -1
78 83 -1 14 38 -1 69 74 78 58
18 52 62 85 11 -1 34 50 58 42
93 76 50 13 44 58 11 52 85 81
55 -1 -1 -1 -1 93 -1 62 99 73
10 64 50 81 96 97 -1 68 46 16
-1 -1 62 71 -1 -1 -1 55 43 22
-1 -1 30 83 28 77 14 11 -1 47
-1 -1 53 -1 86 59 75 23 66 65 |
4 474 1104 |