Задание выполняется с использованием прилагаемых файлов
Квадрат разлинован на 
клеток 
. Исполнитель Оборотень может перемещаться по клеткам вправо и вниз, но когда он делает 
хода в одном направлении (не обязательно подряд), он перевоплощается (если он был в первом стостоянии перевоплощается во второе, если во втором — в первое). При перевоплощении счетчики его ходов обнуляются. В первом своем состоянии по команде вниз Оборотень перемещается на одну клетку вниз, по команде вправо — на одну клетку вправо. Во втором состоянии при таких же командах он перепрыгивает через одну клетку в соответствующем направлении. При попытке выхода за границу квадрата Оборотень умирает. Перед каждым запуском Оборотня в каждой клетке квадрата лежит кусок мяса сытностью от 
до 
. Посетив клетку, Оборотень насыщается и съедает мясо (увеличивает значение насыщенности на сытность мяса); это также относится к начальной и конечной клетке маршрута Оборотня. Изначально значение насыщенности равно сытности мяса в стартовой клетке.
Откройте файл. Определите максимальное значение насыщенности, которого может достичь Оборотень, пройдя из верхней левой клетки в правую нижнюю.
Исходные данные представляют собой электронную таблицу размером 
, каждая ячейка которой соответствует клетке квадрата.
Откроем файл в Excel. Выделим все числа и скопируем их в текстовый документ. Для удобства с помощью комбинации Ctrl + H заменим большие отступы между числами одним пробелом.
Теперь напишем программу для решения задачи:
#хватит 9 ходов вправо и 9 ходов вниз
f = open(’15.txt’)
a = []
for i in range(13):
a.append([int(s) for s in f.readline().split()])
#стартуем из a[0][0], заканчиваем в a[12][12]
#генерируем маршрут из 18 ходов двоичной маской
#вправо - 1 вниз - 0
ma = -10**20
for k in range(2**18):
t = k
mask = []
for j in range(18):
mask.append(t%2)
t//=2
#погнали теперь пробежимся по этой маске!
state = 1
x,y=0,0
right,down = 0,0
s = a[0][0]
for j in range(18):
if mask[j]==0:
y+=state
right+=1
else:
x+=state
down+=1
if right==3 or down==3:
state = 3-state
right = 0
down = 0
if x>12 or y>12:
break
s+=a[x][y]
if x==12 and y==12:
#успешный конец миссии!
if s>ma:
ma = s
break
print(ma)