Задание выполняется с использованием прилагаемых файлов.
Робот стоит в левом верхнем углу прямоугольного поля, в каждой клетке которого записано целое число (-1 или натуральное число).
В некоторых клетках записано число –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
762
1104 |
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 |
|
Исходные данные представлены в виде электронной таблицы (18-01.xlsx) и текстовом файле (18-01.txt)