самый дешевый путь

[Евгений1415]

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

Требуется найти минимальный вес еды в килограммах, отдав которую игрок может попасть в правый нижний угол.

Входные данные
Вводятся два числа N и M — размеры таблицы (1N20, 1M20). Затем идет N строк по M чисел в каждой — размеры штрафов в килограммах за прохождение через соответствующие клетки (числа от 0 до 100).

Выходные данные
Выведите минимальный вес еды в килограммах, отдав которую можно попасть в правый нижний угол.

Примеры
входные данные
5 5
1 1 1 1 1
3 100 100 100 100
1 1 1 1 1
2 2 2 2 1
1 1 1 1 1
выходные данные
11


При чем здесь PHP?
Перемещаю в помощь студентам
И укажи на каком языке

[p51x]

О! Можно бектрекингом побаловаться...

[FPaul]

Или подобием алгоритма Дейкстры.

[Serge_Bliznykov]

погуглите "динамическое программирование черепашка"

Единственное отличие, что в классической задаче идёт поиск максимума, а в данной - поиск минимума.

[FPaul]

Наверное, нужно сначала подсчитать цену перемещения строго вправо и строго вниз. А потом перейти к клетке [2,2] и из неё двигаться вправо и вниз, выбирая самую дешёвую цену из двух возможных. И так до самой последней клетки.

[Croessmah]

Здесь обычным волновым алгоритмом можно решить без проблем

выбирая самую дешёвую цену из двух возможных.

это не даст самого дешевого пути.

[FPaul]

это не даст самого дешевого пути.

Напомню

Выходные данные
Выведите минимальный вес еды в килограммах, отдав которую можно попасть в правый нижний угол.

Т.е. достаточно вычислить "цену".
А волновой здесь неприменим.

[Serge_Bliznykov]

FPaul, ваш алгоритм работать не будет. исходный пример дан уже с этим "подвохом" - из угла два вариант - пойти вниз, стоимость 3 или пойти вправо, стоимость 1
Ваш алгоритм какой путь выберет?!

Ну и не понимаю, о чёт тут спорить.
Эта задача быстро и просто решается через ДП.
Она КЛАССИЧЕСКАЯ азбучная задача для ДП.
Вы хотите изобрести велосипед? А зачем?

ДП - это динамическое программирование

[Croessmah]

Т.е. достаточно вычислить "цену".

Цену пути.
Вот пример:
0 0 0 0 0
1 1 1 1 10
1 1 1 1 0
если по Вашему алгоритму идти, то получим цену 10, а по другому пути - 2.

А волновой здесь неприменим.

Еще как применим, просто волну пускаем в две стороны.
Фактически, алгоритм Дейкстра.

[FPaul]

если по Вашему алгоритму идти, то получим цену 10, а по другому пути - 2.

Нет.
1-й проход от [1,1] вправо и вниз. В клетки матрицы записываем минимальную сумму

0 0 0 0 0
1 1 1 1 10
2 1 1 1 0

2-й проход от [2,2] вправо и вниз. В клетки матрицы записываем минимальную сумму

0 0 0 0 0
1 1 1 1 10
2 2 1 1 0

3-й проход от [3,3] вправо и вниз. В клетки матрицы записываем минимальную сумму

0 0 0 0 0
1 1 1 1 10
2 2 2 2 2

Это и есть ДП - т.к. для выбора оптимального хода используется некая предистория. И именно об этом я и говорил

Наверное, нужно сначала подсчитать цену перемещения строго вправо и строго вниз. А потом перейти к клетке [2,2] и из неё двигаться вправо и вниз, выбирая самую дешёвую цену из двух возможных. И так до самой последней клетки.