1

Суть задачи: Дается матрица 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)

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

1
  • я решал похожую на вашу задачу тут, там же и строил кратчайший путь по матрице.
    – tym32167
    5 ноя 2018 в 13:52

2 ответа 2

3

Поигрался с вашей задачей немного

Начальные данные:

var data = new int[][] { new[] { 5, 9, 4, 3 }, new[] { 3, 1, 6, 9 }, new[] { 8, 6, 8, 12 } };
var dest = new int[data.Length][];
for (int i = 0; i < dest.Length; i++) dest[i] = new int[data[i].Length];

подготовка теблицы

dest[0][0] = data[0][0];
for (var i = 1; i < dest.Length; i++) dest[i][0] = dest[i - 1][0] + data[i][0];
for (var i = 1; i < dest[0].Length; i++) dest[0][i] = dest[0][i - 1] + data[0][i];

заполнение таблицы

for (var i = 1; i < dest.Length; i++)   
    for (var j = 1; j < dest[i].Length; j++)        
        dest[i][j] = Math.Min(dest[i][j - 1], dest[i - 1][j]) + data[i][j];

строим путь

var stack = new Stack<Tuple<int, int>>();
int row = dest.Length-1;
int col = dest[0].Length-1;

stack.Push(Tuple.Create(row, col));

while(row != 0 || col != 0)
{
    if (row ==0)        
        col--;      
    else if (col == 0)      
        row--;              
    else  if (dest[row][col-1] <= dest[row-1][col])     
        col--;                  
    else row--;

    stack.Push(Tuple.Create(row, col));
}   

вывод

Console.WriteLine(dest[dest.Length-1][dest[0].Length-1]);
Console.WriteLine(stack.Count);
foreach (var t in stack) Console.WriteLine($"{t.Item1+1} {t.Item2+1}");

Результат

35
6
1 1
2 1
2 2
3 2
3 3
3 4
2
  • Хе-хе, +, а я перемудрил ;)
    – MBo
    5 ноя 2018 в 15:37
  • @MBo я просто за последние месяцы решал эту задачу раз 10 наверное :)
    – tym32167
    5 ноя 2018 в 15:52
1

Путь можно восстановить если находить стоимость с конца.

Т.е., первый этап поиск минимальной стоимости:

//  field - стоимости перехода в текущую клетку
cost[n - 1, m - 1] = field[n - 1, m - 1];
//  Заполняем последний столбец
for (int i = n - 2; i >= 0; --i)
{
    cost[i, m- 1] = field[i, m - 1] + cost[i + 1, m - 1];
}
//  Заполняем последнюю строку
for (int j = m - 2; j >= 0; --j)
{
    cost[n - 1, j] = field[n - 1, j] + cost[n - 1, j + 1];
}
//  Получаем минимальные стоимости
for (int i = height - 2; i >= 0; --i)
{
     for (int j = width - 2; j >= 0; --j)
     {
         cost[i, j] = Math.Min(cost[i + 1, j], cost[i, j + 1]) + field[i, j];
     }
}
//  В cost[0, 0] - будет минимальная стоимость
Console.WriteLine(cost[0, 0]);

Второй этап, восстановление пути:

//  Начинается путь путь в левой верхней клетке
int x = 0, y = 0;
Console.WriteLine("1 1");

//  Пока не дойдём в правую нижнюю клетку
while (x != n - 1 || y != m - 1)
{
    //  Если выгодней идти вниз
    if (y + 1 == m || x + 1 < n && cost[x + 1, y] <= cost[x, y + 1])
    {
         ++x;
         Console.WriteLine("{0} {1}", x + 1, y + 1);
    }
    //  Если выгодней идти вправо 
    else
    {
        ++y;
        Console.WriteLine("{0} {1}", x + 1, y + 1);
    }
}

Ваш ответ

Нажимая на кнопку «Отправить ответ», вы соглашаетесь с нашими пользовательским соглашением, политикой конфиденциальности и политикой о куки

Всё ещё ищете ответ? Посмотрите другие вопросы с метками или задайте свой вопрос.