Дано поле размером (N, N) клеток (двумерный массив). В каждой клетке написано число – вес клетки. Вес маршрута вычисляется как сумма весов посещенных клеток.
Начальное положение исполнителя — верхняя левая клетка, конечное — нижняя правая.
Если исполнитель может передвигаться только на одну клетку вправо или вниз, то нижеприведенный код верно отобразит ответ для каждой клетки массива:
A = [
[5, 6, 8, 0],
[3, 5, 0, 1],
[4, 4, 1, 1],
[9, 9, 8, 8]
]
for i in range(len(A)):
for j in range(len(A)):
if i > 0 and j > 0:
A[i][j] += min(A[i-1][j], A[i][j-1])
else:
if i > 0:
A[i][j] += A[i-1][j]
else:
if j > 0:
A[i][j] += A[i][j-1]
for i in A:
print(i)
Как будет выглядеть алгоритм, где исполнитель может двигаться на любое количество клеток вправо или вниз?