0

Дано поле размером (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)

Как будет выглядеть алгоритм, где исполнитель может двигаться на любое количество клеток вправо или вниз?

2
  • Почти также будет выглядеть. Вы сами пробовали? Если это учебное задание, приведите вашу попытку решить задачу. 25 июл 2021 в 8:52
  • 1
    В коде из вопроса ошибка в индексах - ширина и высота считаются равными. 25 июл 2021 в 8:52

1 ответ 1

1

Если вы имеете ввиду, то что исполнитель может двигаться прыжками, и при этом не собирать значения на промежутке. То нам нужно не просто сравнивать значения выше, чем клетка и левее, чем клетка. Нам нужно сравнивать все значения левее клетки и выше клетки и выбирать лучшее.

A = [
    [5, 6, 8, 0],
    [3, 5, 0, 1],
    [4, 4, 1, 1],
    [9, 9, 8, 8]
]
dp = [
    [5, 10000, 10000, 10000],
    [10000, 10000, 10000, 10000],
    [10000, 10000, 10000, 10000],
    [10000, 10000, 10000, 10000],
]
for i in range(0,len(A)):
    for j in range(0,len(A)):
        if i-1>=0:
            dp[i][j]=min(dp[i-1][j]+A[i][j],dp[i][j])
        if j-1>=0:
            dp[i][j]=min(dp[i][j-1]+A[i][j],dp[i][j])
for i in dp:
    print(i)

Это был пофикшенный код, у вас выдавал ошибку как это заметили в комментах А это решение::

A = [
    [5, 6, 8, 0],
    [3, 5, 0, 1],
    [4, 4, 1, 1],
    [9, 9, 8, 8]
]
dp = [
    [5, 10000, 10000, 10000],
    [10000, 10000, 10000, 10000],
    [10000, 10000, 10000, 10000],
    [10000, 10000, 10000, 10000],
]
for i in range(0,len(A)):
    for j in range(0,len(A)):
        if i-1>=0:
            x = 10000
            for ll in range(0,i):
                x=min(x,dp[ll][j])
            dp[i][j]=min(x+A[i][j],dp[i][j])
        if j-1>=0:
            x = 10000
            for ll in range(0, j):
                x = min(x, dp[i][ll])
            dp[i][j]=min(x+A[i][j],dp[i][j])
for i in dp:
    print(i)

Ваш ответ

By clicking “Отправить ответ”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Всё ещё ищете ответ? Посмотрите другие вопросы с метками или задайте свой вопрос.