Робот стоит в левом верхнем углу прямоугольного поля, в каждой клетке которого записано целое число. В некоторых клетках записано число −1, в эти клетки роботу заходить нельзя. Для вашего удобства такие клетки выделены тёмным фоном. В остальных клетках записаны положительные числа.
За один ход робот может переместиться на одну клетку вправо или на одну клетку вниз. Клетка, из которой робот не может сделать допустимого хода (справа и снизу находятся границы поля или запрещённые клетки), называется финальной. На поле может быть несколько финальных клеток.
В начальный момент робот обладает некоторым запасом энергии. Расход энергии на запуск робота равен числу, записанному в стартовой клетке.
В дальнейшем расход энергии на шаг из одной клетки в другую равен абсолютной величине разности чисел, записанных в этих клетках.
Задание 1. Определите минимальный начальный запас энергии, который позволит роботу добраться до любой финальной клетки.
Задание 2. Определите минимальный начальный запас энергии, который позволит роботу пройти любым допустимым маршрутом.
Исходные данные записаны в электронной таблице. В ответе запишите два числа: сначала ответ на задание 1, затем ответ на задание 2.
Ответ:
Для поиска минимального значения будем работать с областью B23:U42, так как при расчетах будем использовать исходные значения энергии в каждой клетке.
В ячейку B23 напишем значении =B2.
Для каждой ячейки левого столбца это будет сумма энергии верхней ячейки и абсолютной величине разности чисел: текущей и верхней. Внесем
Для каждой ячейки строки это будет сумма энергии предыдущей ячейки и абсолютной величине разности чисел: текущей и правой. Внесем
Далее в ячейку C24 вставим формулу =МИН(B24+ABS(C3-B3);C23+ABS(C2-C3)) и скопируем за маркер
В ячейки отмеченные серым цветом робот заходить не может, в них поставим заведомо большее число, чтобы при выборе минимального значения в ячейке робот не учитывал эти ячейки.
Финальными клетками для робота могут быть ячейки: F27, L29, Q36, U42.
Определите минимальный начальный запас энергии, который позволит роботу добраться до любой финальной клетки. Для этого введем формулу:=МАКС(F27;L29;Q36;U42). Значение минимального начального запаса энергии, который позволит роботу добраться до любой финальной клетки, — 767.
Определим минимальный начальный запас энергии, который позволит роботу который позволит роботу пройти любым допустимым маршрутом. Для этого произведем замену всех формул с МИН на МАКС. В ячейки отмеченные серым цветом робот заходить не может, в них поставим заведомо меньшее число, чтобы при выборе минимального значения в ячейке робот не учитывал эти ячейки.
Значение минимального начального запаса энергии, который позволит роботу пройти любым допустимым маршрутом, — 2074.
Ответ: 767; 2074.