Словами устроит? :)
Идем из верхнего левого угла и ставим в первом ряду каждой клетке стоимость как сумму клеток слева от нее + она сама (первая горизонталь достижима только слева).
Далее во второй крайняя слева - это сумма стоимости над ней + она сама (только сверху), а все прочие - минимальное значение пути сверху и слева.
И так до конца... Словом, простое динамическое программирование.
Сейчас попробую набросать на C++.
Вот, на коленке, раз уж вас любой язык устраивает... Путь выводится в обратном порядке - от правого нижнего в левый верхний:
#include <iostream>
#include <iomanip>
using namespace std;
int val[3][3] =
{
1, 2, 3, 0, 4, 15, 0, 0, 7
};
int cost[3][3] = { 0 };
int pred[3][3] = {-1}; // 0 - ᢥаег, 1 - б«Ґў
int main(int argc, const char * argv[])
{
cost[0][0] = val[0][0];
for(int c = 1; c < 3; ++c)
{
cost[0][c] = cost[0][c-1] + val[0][c];
pred[0][c] = 1;
}
for(int r = 1; r < 3; ++r)
{
cost[r][0] = cost[r-1][0] + val[r][0];
pred[r][0] = 0;
for(int c = 1; c < 3; ++c)
{
if (cost[r-1][c] < cost[r][c-1])
{
cost[r][c] = val[r][c] + cost[r-1][c];
pred[r][c] = 0;
}
else
{
cost[r][c] = val[r][c] + cost[r][c-1];
pred[r][c] = 1;
}
}
}
cout << "Total cost: " << cost[2][2] << endl;
int r = 2, c = 2;
for(;;)
{
cout << "(" << r << "," << c << ") - ";
if (pred[r][c]) --c; else --r;
if (r == 0 && c == 0)
{
cout << "(0,0)\n";
break;
}
}
}
Шагать можно только вниз или вправо
- вот это интереснее убрать)