Коник. Черепашка

# зчитування інформації з файлу
text=open('konyk.txt','r')
message = text.read()
# запис інформації у список
money=[]
for monety in message.split():
    money.append(int(monety))
print(money)
# записуємо у стек перші два стовпці
stek=[]
stek.append(money[0])
stek.append(money[1])
# записуємо, звідки потрапили на перші два стовпці
konyk=[]
konyk.append(-1)
konyk.append(0)
# від третього (номер 2) і до останнього стовпця
for nomer in range(2,len(money)):
    # тимчасово видаляємо зі стека останній елемент
    temp=stek.pop()
    # видаляємо ще один елемент і рахуємо суму з "передостаннього"
    b=stek.pop()+money[nomer]
    # рахуємо суму з "останнього"
    a=temp+money[nomer]
    # повертаємо тимчасово видалений елемент у стек
    stek.append(temp)
    # записуємо кращу суму та звідки потрапили на стовпець для такої суми
    if a>b:
        stek.append(a)
        konyk.append(nomer-1)
    else:
        stek.append(b)
        konyk.append(nomer-2)
# результат - останній елемент стеку
print(stek.pop())

print(konyk)
# з останнього стовпця (останній номер-1)
k=len(konyk)-1
# поки не дійдемо до першого стовпця, який позначили -1
while konyk[k]!=-1:
    # друкуємо елемент (номер+1 для зручності)
    print(konyk[k]+1)
    # переходимо до елемента, з якого потрапили на цей стовпець
    k=konyk[k]

# матриця зберігається у файлі cherepaha.txt
text=open('cherepaha.txt','r')
# board - матриця з файлу (рядків)
board = []
# n кількість елементів
n=int(text.readline())
# зчитування матриці 
for ryadok in text.readlines():
    board.append(ryadok.split())
    
# поле черепашки (чисел)
pole=[[0 for x in range(n)] for x in range(n)]
# для кожного рядка списку суміжності
k=0
for ryadok in board:
# для кожного елемента рядка
    m=0
    for element in ryadok:
        # записуємо ціле число на поле 
        pole[k][m]=int(element)
        m=m+1
    k=k+1
    
# сума, одержана на цей момент    
gold=[[0 for x in range(n)] for x in range(n)]
gold[0][0]=pole[0][0]

# маршрут черепашки
che=[[0 for x in range(n)] for x in range(n)]
che[0][0]=0

# перебираємо всі рядки та стовпці
for i in range(n):
    for j in range(n):
        # рухаємось вниз до i+1 (тобто з клітинки i-1)
        gold[i][j]=gold[i-1][j]+pole[i][j]
        che[i][j]=1
        # перевірка, чи не краще було би пройти вправо
        if gold [i-1][j] + pole [i][j] < gold [i][j-1] + pole[i][j]:
            # рухаємось вправо
            gold [i][j]= gold [i][j-1] + pole[i][j]
            che[i][j]=2
            
# друк вмісту останньої клітинки - накопичена сума            
print(gold[4][4])

# друк маршруту - з останньої клітинки
i= 4
j= 4
# поки не дійдемо до першої
while (i > 0) or (j > 0):
    # якщо в клітинці стоїть 2, то потрапили сюди, рухаючись вправо
    if che[i][j] == 2 :
        print('вправо',gold[i][j])
        # переходимо до клітинки ліворуч
        j=j-1
    # інакше - потрапили рухаючись вниз
    else:
        print('вниз ',gold[i][j])
        # переходимо до клітинки вище
        i=i-1

Розв'язок задачі