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