Робот стоит в левом нижнем углу прямоугольного поля, в каждой клетке которого записано целое число. В некоторых клетках записано число −1, в эти клетки роботу заходить нельзя. Для вашего удобства такие клетки выделены тёмным фоном. В остальных клетках записаны положительные числа.
За один ход робот может переместиться на одну клетку вправо или на одну клетку вверх. Клетка, из которой робот не может сделать допустимого хода (справа и сверху находятся границы поля или запрещённые клетки), называется финальной. На поле может быть несколько финальных клеток.
В начальный момент робот обладает некоторым запасом энергии. Расход энергии на запуск робота равен числу, записанному в стартовой клетке.
В дальнейшем расход энергии на шаг из одной клетки в другую равен абсолютной величине разности чисел, записанных в этих клетках.
Задание 1. Определите минимальный начальный запас энергии, который позволит роботу добраться до любой финальной клетки.
Задание 2. Определите минимальный начальный запас энергии, который позволит роботу пройти любым допустимым маршрутом.
Исходные данные записаны в электронной таблице. В ответе запишите два числа: сначала ответ на задание 1, затем ответ на задание 2.
Ответ:
Построенная карта для робота в txt формате: карта к 18 txt.txt
Приведём решение на языке Python.
import re; from functools import cache
@cache
def bot(s, h, p, z):
if z in ['QA','QB','QC', 'QD']:
global QA, QB, QC, QD
if z == 'QA': QA += [s]
if z == 'QB': QB += [s]
if z == 'QC': QC += [s]
if z == 'QD': QD += [s]
return 1
bot(s+abs(y(h, p)[0] - y(h-1, p)[0]), h-1, p, y(h-1, p)[1]) if z != 'H' else 0
bot(s+abs(y(h, p)[0] - y(h, p+1)[0]), h, p+1, y(h, p+1)[1]) if z != 'P' else 0
f = list(map(lambda x: x.split(), open('карта к 18 txt.txt').readlines()))
y = lambda i0, i1: [int(re.sub(r'[A-Z]', '', f[i0][i1])), re.sub(r'\d', '', f[i0][i1])]
QA, QB, QC, QD = [], [], [], []; bot(int(f[len(f)-1][0]), len(f)-1, 0, 0)
print(max(min(_) for _ in (QA, QB, QC, QD)), max(QA + QB + QC + QD))
Ответ: 719; 2052.