Суть задачи:
Дается матрица NxM нужно найти путь из левого верхнего угла в правый нижний, двигаясь либо на соседнюю клетку вниз, либо вправо, каждый шаг стоит столько у.е. сколько записано в матрице.
Найти самый "дешевый" путь не проблема, вводим данные, начальные значение для нулевой строки и нулевого столбца и просчитываем матрицу результатов, где d[n-1][m-1] ответ о цене пути.
for (int i = 1; i < n; i++)
{
for (int j = 1; j < m; j++)
{
d[i, j] = Math.Min(d[i - 1, j], d[i, j - 1]) + arr[i, j];
}
}
НО! нужно сохранить и(или хотя бы) вывести сам этот путь
например:
вход:
3 4
5 9 4 3
3 1 6 9
8 6 8 12
выход:
35
6
1 1
2 1
2 2
3 2
3 3
3 4
Была такая попытка
long x = 0, y = 0;
StringBuilder path = new StringBuilder("");
appends(ref path, 0, 0);
while (true)
{
if (x == m - 1 && y == n - 1) break;
long a, b;
if (y < n - 1) a = d[y + 1, x];
else a = Int64.MaxValue;
if (x < m - 1) b = d[y, x + 1];
else b = Int64.MaxValue;
if (a > b)
{
if (x < m - 1)
x += 1;
appends(ref path, y, x);
}
else
{
if (y < n - 1)
y += 1;
appends(ref path, y, x);
}
}
Где appends()
считает количество вызовов(т.е. кол-во шагов) и приписывает в path (y+1) + " " + (x+1)
На простых примерах все работает, но есть такие тесты (которые я заранее не знаю) на которых код отвечает не правильно, где и в чем может быть ошибка? или как лучше выполнить эту задачу?