необходимо написать программу

[Дарья0108]

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

[digitalis]

Похоже на динамическое программирование, алгоритм Беллмана. Это во ФРИЛАНСЕ стоит больших денег, думаю. Или просто тупо полным перебором...

[Arigato]

Задачка не тривиальная, хотя во Фрилансе решить не проблема.

[ViktorR]

Задача не простая, но и не столь уж сложная.
На этом форуме предлагал решение подобной задачи с поиском пути, когда собирается максимальное число зёрен (в каком то индийском храме ???).
Но алгоритм пройдёт и для поиска минимального решения.

Надо начать путь с конечной точки. В соответствии с условием задачи, в эту точку попасть можно только с трёх соседних клеток.
Находим сумму значения в текущей клетке и значения в соседних.
Вписываем минимальную сумму.
Двигаемся по горизонтали. каждая клетка граничит с тремя клетками (учитываем движение по диагонали).
Заполняем клетки минимальной суммой. Далее поднимаемся в следующий ряд и т.д.
После заполнения всех клеток получим ту сумму, которая будет возможной минимальной.
Далее очевиден путь или даже пути, по которым следует двигаться.

PS: Это тут: https://programmersforum.ru/showthre...335585&page=10
Код на Python. Там есть ссылка на книжку. В книге есть код на Паскаль, но он неверный.
Думаю, что ТС следует подумать, может ли справиться с задачей или во фриланс.
Собственно какова цель задания?

[digitalis]

Сообщение от ViktorR

Собственно какова цель задания?

Получить зачёт, вестимо