Оптимальные маршруты
(Время: 1 сек. Память: 32 Мб Сложность: 46%)
Робот стоит в левом нижнем углу прямоугольного поля, в каждой клетке которого записано натуральное число. За один ход робот может переместиться на одну клетку вправо или на одну клетку вверх. Расход энергии на запуск робота равен числу, записанному в стартовой клетке. В дальнейшем расход энергии на шаг из одной клетки в другую равен абсолютной величине разности чисел, записанных в этих клетках.
Определите минимальный и максимальный расход энергии при переходе робота в правую верхнюю клетку поля. В ответе запишите два числа: сначала минимальный расход энергии, затем – максимальный. Исходные данные записаны в электронной таблице.
Входные данные
Входной файл INPUT.TXT содержит таблицу N×M, состоящую из N строк, в каждой строке записано M целых чисел Aij (1 ≤ Aij ≤ 99), разделенных символом «;» (точка с запятой). Гарантируется, что суммарное количество чисел в таблице не превосходит 105 (1 ≤ N×M ≤ 105).
Выходные данные
В выходной файл OUTPUT.TXT выведите два целых числа – минимальный и максимальный расход энергии при переходе робота в правую верхнюю клетку.
Примеры
| № | INPUT.TXT | OUTPUT.TXT |
|---|
| 1 | 45;54;20;86
68;46;27;71
83;26;98;82
23;80;25;48 | 198 356 |
| 2 |
47;2;50;55;56;75;82;41;6;88;56;70;31;39;89
33;70;65;70;72;49;26;69;82;13;2;65;22;65;81
15;19;15;54;51;89;95;80;16;77;61;6;75;53;79
84;15;52;69;88;35;15;71;2;3;45;10;7;28;82
92;44;32;4;58;23;20;64;72;70;57;84;61;27;78
44;60;65;37;67;98;22;42;95;31;18;18;44;39;43
79;77;38;66;76;28;58;67;9;43;20;94;69;82;89
57;6;73;49;46;46;84;84;85;73;66;23;99;69;78
53;37;57;7;36;64;18;66;30;21;86;96;30;79;81
2;92;15;7;43;90;59;74;44;35;57;64;57;21;6
22;21;16;85;21;78;10;29;6;90;35;76;74;7;26
77;10;56;13;67;93;60;44;69;45;46;13;76;5;42
25;88;18;65;21;45;64;92;95;18;6;83;90;18;28
6;6;77;71;71;2;65;64;16;75;16;39;52;25;15
61;73;52;18;51;88;92;57;67;19;2;78;92;33;36
| 479 1599 |
Пояснение к примеру №1
При указанных входных данных минимальное значение получится при движении по маршруту
23 → 83 → 68 → 46 → 27→ 71→ 86.
Расход энергии на этом пути равен
23 + (83 – 23) + (83 – 68) + (68 – 46) + (46 – 27) + (71 – 27) + (86 – 71) = 198.
Максимальное значение получится при движении по маршруту
23 → 83 → 26 → 98 → 27 → 20→ 86.
Расход энергии в этом случае равен
23 + (83 – 23) + (83 – 26) + (98 – 26) + (98 – 27) + (27 – 20) + (86 – 20) = 356.
Поэтому в качестве ответа следует записать числа 198 и 356.
Пояснение к примеру №2
Файл с заданием в формате Excel: 18.xlsx .
Файл с решением в формате Excel: 18_solution.xlsx .
Для отправки решения задачи необходимо зарегистрироваться и авторизоваться!
| 
