Поиск маршрута с минимальным весом

[ViktorR]

Задача от Дарья0108

Дано прямоугольное поле размером n*m клеток. Можно совершать шаги длиной в одну клетку вправо, вниз или по диагонали вправо-вниз. В каждой клетке записано некоторое натуральное число. Необходимо попасть из верхней левой клетки в правую нижнюю. Вес маршрута вычисляется как сумма чисел со всех посещенных клеток. Необходимо найти маршрут с минимальным весом.

Задача интересная, подобная ей тут решалась:
https://programmersforum.ru/showthre...335585&page=10
Так как язык не заказан, сделал в Python

import numpy as np

def IntermediateData(np_m):
    ''' Подготовим вспомогательный массив
        на основе массива np_m
    '''
    (n, m) = np_m.shape                         # Размер массива 
    np_tmp = np.zeros((n, m), dtype = int)      # Используем вспомогательный массив
    np_tmp[n-1, m-1] = np_m[n-1, m-1]           # Правый нижний угол
    
    for j in range(m - 2, -1, -1):              # нижняя строка
        np_tmp[n - 1, j] = np_tmp[n - 1, j + 1] + np_m[n - 1, j]
            
    for j in range(n - 2, -1, -1):              # правый столбец
        np_tmp[j, m - 1] = np_tmp[j + 1, m - 1] + np_mas[j, m - 1]
    
    for i in range(n - 2, -1, -1):              # i - номер строки
        for j in range(m - 2, -1, -1):          # j  - номер столбца
           # Возможный вес
            np_tmp[i, j] = np_mas[i, j] + min(np_tmp[i + 1, j], np_tmp[i + 1, j + 1], np_tmp[i, j + 1])
    return np_tmp

def FindTrace(np_m):
    """ Поиск пути
    """
    (n, m) = np_m.shape                        # Размер массива
    np_str = np.full((n, m), '.', dtype = str) # Вспомогательный массив заполним '.'
    np_str[0, 0] = 'Q'                         # Верхняя левая клетка
    
    i = 0; j = 0                               # i - номер строки, j - номер столбца
    while True:
        ij_list = [[i, j + 1],[i + 1, j + 1], [i + 1, j]]              # Список возможных переходов
        m_list = [np_m[i, j + 1], np_m[i + 1, j + 1], np_m[i + 1, j]]  # Список значений
        i, j = ij_list[m_list.index(min(m_list))]                      # Следующая клетка маршрута
        np_str[i, j] = 'Q'
        if i == n - 1:                # Достигли нижней строки
            while j <= m - 1:         # Двигаемся до правой границы
                np_str[i, j] = 'Q'    # только вправо
                j += 1
            break
        if j == m - 1:                # Достигли правой границы
            while i <= n - 1:         # Двигаемся до нижней границы
                np_str[i, j] = 'Q'    # только вниз
                i += 1
            break
    return np_str                     # массив маршрута

# ======= Main =======
n = 5      # число строк
m = 7      # число столбцов
zmax = 10  # максимальный вес клетки

np_mas = np.random.randint(0, zmax, (n, m)) # Инициализация массива чисел
print(np_mas)                               # Основной массив

np_t = IntermediateData(np_mas)             # Посчитаем вес маршрута
# print('\n', np_t)                         # Тестовая печать маршрута
print('Вес маршрута: ', np_t[0,0])

print('Путь с минимальным весом маршрута:')
print(FindTrace(np_t))    # Печать карты маршрута

Пример вывода:

[[1 8 7 7 4 6 6]
 [8 4 0 6 1 4 6]
 [5 9 4 6 5 4 8]
 [1 0 0 0 3 2 6]
 [9 3 2 4 4 7 9]]
Вес маршрута:  23
Путь с минимальным весом маршрута:
[['Q' '.' '.' '.' '.' '.' '.']
 ['.' 'Q' 'Q' '.' '.' '.' '.']
 ['.' '.' 'Q' '.' '.' '.' '.']
 ['.' '.' '.' 'Q' 'Q' 'Q' '.']
 ['.' '.' '.' '.' '.' '.' 'Q']]