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

А может быть стоит решать задание типа 18 программно???

Задание типа 18 предполагается решать с помощью табличного редактора. Это в целом правильно

Но, после решения задания типа 18 из варианта Статграда, ученик Фома стал требовать решения этого задания с помощью программы.

Условие задания (демоверсия 2025)

Квадрат разлинован на N × N клеток (1 < N < 30). Исполнитель Робот может перемещаться по клеткам, выполняя за одно перемещение одну из двух команд: вправо или вниз.

По команде вправо Робот перемещается в соседнюю правую клетку,
по команде вниз – в соседнюю нижнюю.

Квадрат ограничен внешними стенами. Между соседними клетками квадрата также могут быть внутренние стены. Сквозь стену Робот пройти не может. Перед каждым запуском Робота в каждой клетке квадрата лежит монета достоинством от 1 до 100. Посетив клетку, Робот забирает монету с собой; это также относится к начальной и конечной клеткам маршрута Робота. В «угловых» клетках поля - тех, которые справа и снизу ограничены стенами, Робот не может продолжать движение, поэтому накопленная сумма считается итоговой. Таких конечных клеток на поле может быть несколько, включая правую нижнюю клетку поля. При разных запусках итоговые накопленные суммы могут различаться.

Определите максимальную и минимальную денежные суммы, среди всех возможных итоговых сумм, которые может собрать Робот, пройдя из левой верхней клетки в конечную клетку маршрута.
В ответе укажите два числа (в строку через пробел) - сначала максимальную сумму, затем минимальную.
Исходные данные представляют собой электронную таблицу размером N × N,
каждая ячейка которой соответствует клетке квадрата. Внутренние и внешние стены обозначены утолщёнными линиями

План подготовки и решения

Подготовка данных в текстовом формате: создаем таблицу с данными и таблицу "запретов"
Программная обработка

Этап А.

Открытие таблици в табличном редакторе Ctr+A - Ctr+C - переход в блокнот - Ctr+V - Ctr+S и получаем таблицу в текстовом формате
Создание таблицы "запретов". Было предложено несколько вариантов, приведем один (не самый "быстрый", но "понятный")

создаем копию таблицы, заполняем знаком "о", и "наносим формат"
возле "стенок" заносим знаки "x" и "y" (по правилам ходов, так же как делали бы это "руками")

исходная таблица таблица запретов

Что-то похожее делается при занесении формул. Важно понять, сколько времени уходит на такую подготовку?
(На создание двух файлов ушло не более 3-х минут)

Этап В можно разбить на несколько подэтапов

чтение данных
определение "угловых" клеток
заполнение таблиц для "минимального" и "произвольного" обхода

def fread(fname): # программа для "стандартного" чтение данных из файла
  A = [] 
  for ss in open(fname):
    A.append(list(ss.split()))
  return A

def isnext(i,j):
  if (i+1 < len(Tabl)) and (Tzap[i+1][j] != 'y') : 
    return True
  if (j+1 < len(Tabl[0])) and (Tzap[i][j+1] != 'x') : 
    return True
  return False

fnameT = '18_17874_tab.txt'
fnameZ = '18_17874_zzz.txt'
Tabl = fread(fnameT)
Tzap = fread(fnameZ)
N, M = len (Tabl), len(Tabl[0]) 
print('В таблице {} строк и {} столбцов'.format(N, M))
End = [] 
for i in range(N):
  for j in range(M):
    if isnext(i,j) == False :
      End.append((i,j))
print('Угловых клеток', len(End))
print(*End)

Чтение из файлов можно организовать разными способами (в том числе и в одну строку). Выделение этого процесса в подпрограмму может "пригодиться"при решении других заданий КЕГЭ. Проверку на "угловую" точку желательно выделить в подпрограмму, поскольку это позволяет "настраивать" алгоритм на разные правила "движения" робота и "перемещать" её в коде. В дальнейшем коде "спрячем" эти подпрограммы.
Далее надо

Создать две таблицы V и W для получения результатов минимального и произвольного обходов
Начальное заполнение значениями None
Заполнить координаты стартовой клетки (ii,jj), значения стартовой клетки в таблицах V, W
Заполнить все клетки таблиц V, W (путем обхода)

Можно вначале решить задание для минимального обхода, затем исправить копию программы и найти второй ответ.

fnameT = '18_17874_tab.txt'
fnameZ = '18_17874_zzz.txt'
Tabl = fread(fnameT)
Tzap = fread(fnameZ)
N, M = len (Tabl), len(Tabl[0]) 
End = [] 
for i in range(N):
  for j in range(M):
    if isnext(i,j) == False :
      End.append((i,j))
V = [ [None] * M for i in range(N)]
W = [ [None] * M for i in range(N)]
ii, jj = 0, 0 # Робот стартует из клетки (0,0)
V[ii][jj] = W[ii][jj] = int(Tabl[ii][jj]) # копируем значение стартовой точки
jj = 1 # переход к первой точке заполнения
while (ii<N): # двойной цикл организован через один while
  rx_v, rx_w = None, None # мин и макс по х (слева)
  if Tzap[ii][jj] != 'x' and jj > 0 : # есть "предок" по x 
    rx_v, rx_w = V[ii][jj-1], W[ii][jj-1]  # фиксируем значения
  ry_v, ry_w = None, None # мин и макс по y (сверху)
  if Tzap[ii][jj] != 'y' and ii > 0 : # есть "предок" по y
    ry_v, ry_w = V[ii-1][jj], W[ii-1][jj] # фиксируем значения
  r_v, r_w = rx_v, rx_w # обобщение по x, y
  if (ry_v != None) and (r_v == None or ry_v < r_v): # по у лучше
    r_v = ry_v
  if (ry_w != None) and (r_w == None or ry_w > r_w): # по у лучше
    r_w = ry_w
  if r_v != None : # клетка достижима - фиксируем результат
    V[ii][jj] = int(Tabl[ii][jj]) + r_v 
  if r_w != None : # клетка достижима - фиксируем результат
    W[ii][jj] = int(Tabl[ii][jj]) + r_w
  # получение следующего состояния  
  if jj+1 < M : # можем увеличить по абциссе 
    jj += 1
  else : # увеличиваем ординату, абциссу обнуляем
    ii, jj = ii+1, 0
ans1 = min([V[e[0]][e[1]] for e in End])
ans2 = max([W[e[0]][e[1]] for e in End])
print(ans2 , ans1)

Решение есть (около 50 строк кода), но

плохо читается - много квадратных скобок
не очень понятно, что делается

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

Таблица с данными и таблица запретов при чтении заносятся в словари
(словарь упрощает проверку на выход за пределы таблицы)
Для храниения результатов также используются словари
(в них будем заносить только "достижимые" клетки)
Обход клеток оставим без изменений

Для начала объединим чтение из файлов и заполнение словаря (для Таблицы) и множест (для Запретов) в одну программу

def freads(fname_1, fname_2): # программа чтение данных из файлов
  f2 = open(fname_2) # открытие файла с запретами
  n, m = 0, 0 # инициализация размеров таблицы
  for s in open(fname_1): # построчное чтение из файла
    ss1 = list(s.split()) # создание списка строки
    ss2 = list(f2.readline().split()) # "параллельное" чтение
    for j in range (len(ss1)) : # пробег по строке
      Tabl[(n, j)] = int(ss1[j]) # фиксация результатов
      if 'x' in ss2[j] : Zap_x.add((n,j))
      if 'y' in ss2[j] : Zap_y.add((n,j))
    n, m =n + 1,  max(m, len(ss1)) # фиксация текущих размеров таблицы
  return (n, m) # возврат результатов

def isnext(pos):
  p_j = (pos[0], pos[1] + 1) # сл. позиция справа
  p_i = (pos[0] + 1, pos[1]) # сл. позиция снизу
  if (p_j in Tabl) and not (p_j in Zap_x) : 
    return True # можем пойти вправо
  if (p_i in Tabl) and not (p_i in Zap_y) : 
    return True # можем пойти вниз
  return False

fnameT = '18_17874_tab.txt' # имя файла с Таблицей
fnameZ = '18_17874_zzz.txt' # имя файла с Запретами
Tabl = dict() # инициализация словаря Таблицы
Zap_x, Zap_y = set(), set() # инициализация множеств Запретов
nm = freads(fnameT,fnameZ) # получаем размеры таблицы, заполняем словарь и множества
print('В таблице {} строк и {} столбцов'.format(*nm))
End = [] # список для "угловых" клеток
for pos in Tabl:
  if isnext(pos) == False :
      End.append(pos)     
print('Угловых клеток', len(End))
print(*End)

Добавим обход Таблицы и заполнение итоговых словарей. Значение в итоговые словари будем заносить только для "достижимых" клеток (то есть только для тех, в которые можно попасть)

# две подпрограммы скрыты
fnameT = '18_17874_tab.txt' # имя файла с Таблицей
fnameZ = '18_17874_zzz.txt' # имя файла с Запретами
Tabl = dict() # инициализация словаря Таблицы
Zap_x, Zap_y = set(), set() # инициализация множеств Запретов
nm = freads(fnameT,fnameZ) # получаем размеры таблицы, заполняем словарь и множества
End = [] # список для "угловых" клеток
for pos in Tabl:
  if isnext(pos) == False :
      End.append(pos)
pos  = (0, 0) # инициализация стартовой точки
V = {pos : Tabl[pos]} # инициализация словаря для поиска "минимального" 
W = {pos : Tabl[pos]} # инициализация словаря для поиска "максимального"
pos = (pos[0],pos[1]+1) # переход к первой точке заполнения
while (pos[0] < nm[0]): # цикл организован по позиции через один while
  p_x = (pos[0], pos[1] - 1) # предок по x
  p_y = (pos[0]- 1, pos[1]) # предок по y
  pred_v, pred_w = set(), set() # инициализация предков по V и W 
  if not (pos in Zap_x) and (p_x in V) : # проверка слева
    pred_v.add(V[p_x]) # добавление значения по предку x
    pred_w.add(W[p_x]) 
  if not (pos in Zap_y) and (p_y in V) : # проверка сверху
    pred_v.add(V[p_y]) # добавление значения по предку y
    pred_w.add(W[p_y]) 
  if pred_v : # проверка на достижимость и фиксация
    V[pos] = min(pred_v) + Tabl[pos]
    W[pos] = max(pred_w) + Tabl[pos]
  # получение следующего состояния  
  if pos[1]+1 < nm[1] : # можем увеличить по абциссе 
    pos =  (pos[0],pos[1]+1)
  else : # увеличиваем ординату, абциссу обнуляем
    pos = (pos[0]+1, 0) 
ans1 = min([V[pos] for pos in End])
ans2 = max([W[pos] for pos in End])
print(ans2 , ans1)

Удалось написать программу с использованием словарей и множеств.
Что получили:

Код программы стал более "сложным", но и более "читаемым"
Освоен перебор элементов таблицы через один цикл while
(будет проще перейти на другие способы движения)
Решение разбито на этапы, поиск результатов ведется "параллельно"
(можно копировать строки)
Упрощен способ получения результатов
(вначале получаем значения предков, затем вычисляем результат)

"Угловые" клетки, для отладки, лучше искать вначале но, при наличии "недостижимых угловых" клеток, надо перенести в основной блок
Приведем изменения кода для "обратной" задачи:

Робот стартует в правой нижней клетке и может передвигаться вверх и налево
для файла '18_17874_new.xls' (изменили стенки)

def freads(fname_1, fname_2): 
  f2 = open(fname_2) 
  n, m = 0, 0 
  for s in open(fname_1): 
    ss1 = list(s.split()) 
    ss2 = list(f2.readline().split()) 
    for j in range (len(ss1)) : 
      Tabl[(n, j)] = int(ss1[j]) 
      if 'x' in ss2[j] : Zap_x.add((n,j))
      if 'y' in ss2[j] : Zap_y.add((n,j))
    n, m =n + 1,  max(m, len(ss1)) 
  return (n, m) 
def isnext(pos):
  p_j = (pos[0], pos[1] - 1) # изменили значение
  p_i = (pos[0] - 1, pos[1]) # изменили значение
  if (p_j in Tabl) and not (p_j in Zap_x) :  return True 
  if (p_i in Tabl) and not (p_i in Zap_y) :  return True 
  return False 
fnameT = '18_17874_tab.txt' 
fnameZ = '18_17874_xyz.txt' # другой файл запретов 
Tabl = dict() 
Zap_x, Zap_y = set(), set() 
nm = freads(fnameT,fnameZ) 
pos  = (nm[0] - 1, nm[1] - 1) # изменили значение
V = {pos : Tabl[pos]}  
W = {pos : Tabl[pos]} 
End = [] # перенесли в основной блок
pos = (pos[0],pos[1]+1) 
while (pos[0] >= 0): # изменили условие остановки 
  p_x = (pos[0], pos[1] + 1) # изменили знак 
  p_y = (pos[0]+ 1, pos[1]) # изменили знак
  pred_v, pred_w = set(), set()  
  if not (pos in Zap_x) and (p_x in V) : 
    pred_v.add(V[p_x]) 
    pred_w.add(W[p_x]) 
  if not (pos in Zap_y) and (p_y in V) : 
    pred_v.add(V[p_y]) 
    pred_w.add(W[p_y]) 
  if pred_v : 
    V[pos] = min(pred_v) + Tabl[pos]
    W[pos] = max(pred_w) + Tabl[pos]
    if isnext(pos) == False : # перенесли сюда проверку на "угол"
      End.append(pos)
  if pos[1] > 0 : # изменили переход к следующему  
    pos =  (pos[0],pos[1] - 1)
  else : 
    pos = (pos[0] - 1, nm[1] - 1) 
ans1 = min([V[pos] for pos in End])
ans2 = max([W[pos] for pos in End])
print(ans2 , ans1)

Подведём итоги:
Решение занимает около 50 строк кода и значит уложиться в отведённые 8 минут сложно. Следовательно, основным способом должен быть "ручной" (используем табличный редактор). Программный способ нужно понять и освоить, потому что:

При ручном способе "несложно" допустить ошибку, проверку (если на это будет время) лучше делать программно
Возможно, будет не очень "удобная" таблица (много стенок, угловых клеток, сложные ходы и т.п.)
Вы не очень сильны в "табличных процессорах"
Если запреты будут не ввиде стенок (например так, как в варианте Статграда)
Для проверки результата и поиска "проблем решения" на тренировочных заданиях
Если фрагменты кода будут применяться при решении других заданий КЕГЭ

Рекомендуется написать своё решение, используя:

привычные Вам обозначения переменных и подпрограмм
разбиение на блоки и "визуальные" проверки результатов
возможно, удобнее будет вначале найти одно из значений ответа, а затем в копии программы заменить "одно сравнение"
сделать вывод о применимости "программного" подхода к решению не ранее 5-7 попыток написания кода

# Код поиска только минимального (для тренировок и улучшений) 
def freads(fname_1, fname_2): #подпрограмма чтения данных 
  f2 = open(fname_2) 
  n, m = 0, 0 
  for s in open(fname_1): 
    ss1 = list(s.split()) 
    ss2 = list(f2.readline().split()) 
    for j in range (len(ss1)) : 
      Tabl[(n, j)] = int(ss1[j]) 
      if 'x' in ss2[j] : Zap_x.add((n,j))
      if 'y' in ss2[j] : Zap_y.add((n,j))
    n, m =n + 1,  max(m, len(ss1)) 
  return (n, m) 
def isnext(pos): # подпрограмма проверки на "угловую"
  p_j = (pos[0], pos[1] - 1) # изменили значение
  p_i = (pos[0] - 1, pos[1]) # изменили значение
  if (p_j in Tabl) and not (p_j in Zap_x) :  return False 
  if (p_i in Tabl) and not (p_i in Zap_y) :  return False 
  return True # Клетка угловая 
fnameT = '18_17874_tab.txt' # файл с данными
fnameZ = '18_17874_xyz.txt' # файл запретов 
Tabl = dict() # словарь для запретов
Zap_x, Zap_y = set(), set() 
nm = freads(fnameT,fnameZ) 
pos  = (nm[0] - 1, nm[1] - 1) # из нижнего правого
V = {pos : Tabl[pos]}  
End = [] # перенесли в основной блок
pos = (pos[0],pos[1]+1) 
while (pos[0] >= 0): # изменили условие остановки 
  p_x = (pos[0], pos[1] + 1) # изменили знак 
  p_y = (pos[0]+ 1, pos[1]) # изменили знак
  pred_v = set() # место для предков  
  if not (pos in Zap_x) and (p_x in V) : 
    pred_v.add(V[p_x]) 
  if not (pos in Zap_y) and (p_y in V) : 
    pred_v.add(V[p_y]) 
  if pred_v : 
    V[pos] = min(pred_v) + Tabl[pos] # выбор МИНИМАЛЬНОГО
    if isnext(pos) : # клетка "угловая"
      End.append(pos)
  if pos[1] > 0 : # изменили переход к следующему  
    pos =  (pos[0],pos[1] - 1)
  else : 
    pos = (pos[0] - 1, nm[1] - 1) 
ans = min([V[pos] for pos in End])
print(ans)

# для тренировок

Разумные предложения от учеников (после тренировок на заданиях прошлых лет)

Писать программу только для одного из поисков
Заносить ограничения сразу в таблицу (заменив числа на x, y) и записывать их перед стенками.
Сократить имена переменных

Прикрепленные файлы
18_17874.xls
18_17874_new.xls
18_17874_tab.txt
18_17874_xyz.txt
18_17874_zzz.txt

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

Печать

исходная таблица	таблица запретов