Статья Автор: Лебедев Дмитрий

Разбор демо варианта типа 18

Задание 3-1

Робот стоит в левом верхнем углу прямоугольного поля, в каждой клетке которого записано целое число. В некоторых клетках записано число –1, в эти клетки роботу заходить нельзя. Для вашего удобства такие клетки выделены тёмным фоном. В остальных клетках записаны положительные числа. За один ход робот может переместиться на одну клетку вправо или на одну клетку вниз.
Клетка, из которой робот не может сделать допустимого хода (справа и снизу находятся границы поля или запрещённые клетки), называется финальной. На поле может быть несколько финальных клеток. В начальный момент робот обладает некоторым запасом энергии. Расход энергии на запуск робота равен числу, записанному в стартовой клетке. В дальнейшем расход энергии на переход в каждую следующую клетку равен числу, записанному в этой клетке.

Задание 1. Определите количество финальных клеток.
Задание 2. Определите минимальный начальный запас энергии, который позволит роботу добраться до любой финальной клетки.
Задание 3. Определите минимальный начальный запас энергии, который позволит роботу пройти любым допустимым маршрутом

Входные данные.
Исходные данные представлены в двух форматах (тестовом файле, электронной таблице)
Выходные данные
Три числа - ответы на задание (каждое число в отдельной строке)

входные данные

выходные данные

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
474
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

sss

По условию, есть одна "стартовая" точка и несколько "финальных".
Для решения удобно применить метод "сверху-вниз" с запуском от всех "финальных" позиций.
Определим "финальные" позиции с помощью подпрограммы isnext(pos)

Определение максимальных сумм.
Напишем программу, осуществляющую "динамическую рекурсию" методом "сверху вниз" с поиском максимальной и минимальной сумм пути.
Для этого будем

использовать "обратные" команды (влево заменяет вправо, ввниз заменяет вверх)
значения будем записывать в словарь Dpmax и Dpmin
полученные результаты добавим в End_pos

Программы поиска максимального и минимального пути - программы-близнецы, поэтому одну убрали

# программа f18max скрыта 
def isnext(pos) :
  # возвращает True если позиция финальная, Иначе False
  if ((pos[0]+1,pos[1]) in Tabl) or ((pos[0],pos[1]+1) in Tabl) :
    return False 
  return True
def f18max(pos) : # поиск максимальной стоимости
  if not(pos in Tabl ) : # позиция недостижима 
    return None
  if pos in Dp_max : # позиция уже обработана
    return Dp_max[pos] 
  a = f18max((pos[0] - 1, pos[1])) # значение ПРЕДКА слева
  b = f18max((pos[0], pos[1] - 1)) # значение ПРЕДКА сверху
  r = a # выбор ПРЕДКА с максимальным значением 
  if b and (r == None or b > r) : 
    r=b
  Dp_max[pos] = Tabl[pos] + r # фиксация и возврат значения
  return Dp_max[pos]

def f18min(pos) : # поиск максимальной стоимости
  if not(pos in Tabl ) : # позиция недостижима 
    return None
  if pos in Dp_min : # позиция уже обработана
    return Dp_min[pos] 
  a = f18min((pos[0] - 1, pos[1])) # значение ПРЕДКА слева
  b = f18min((pos[0], pos[1] - 1)) # значение ПРЕДКА сверху
  r = a # выбор ПРЕДКА с минимальным значением 
  if b and (r == None or b < r) : 
    r = b
  Dp_min[pos] = Tabl[pos] + r # фиксация и возврат значения
  return Dp_min[pos]
# Подготовительный этап
Tabl = dict() 
N, M = 0, 0 
#for ss in open ('18_24-10.txt') : 
for ss in open ('18-01_10.txt') : 
  A = list(map(int, ss.split())) 
  for j in range(len(A)): 
    if A[j] >= 0 : 
      Tabl[(N,j)] =  A[j] 
  N, M = N + 1, max(M, len(A))   
# Определение финальных позиций
End_pos = dict()  
for pos in Tabl : 
  if isnext(pos) : 
    End_pos[pos] = None 
print(len(End_pos))
# Определение стоимостей прохода
Dp_max = {(0,0) : Tabl[(0,0)]}
Dp_min = {(0,0) : Tabl[(0,0)]}
for  pos in End_pos :
  ans0 = f18min(pos)
  ans1 = f18max(pos)
  End_pos[pos]= (ans0,ans1)
print(*End_pos.items(), sep = '\n')
#'''

Прикрепленные файлы
18-00.txt
18-01_10.txt
18_24-10.txt

Чтобы оставить комментарий нужна авторизация

Печать