The essence of the problem: The NxM matrix is ​​given; you need to find a path from the upper left to the lower right, moving either to the next cell down or to the right, each step costs so much. how much is written in the matrix.
Find the most "cheap" way is not a problem, enter the data, the initial value for the zero row and the zero column and calculate the result matrix, where d [n-1] [m-1] is the answer about the price of the path.

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]; } }

BUT! you need to save and (or at least) withdraw this path yourself
eg:
entrance:

 3 4 5 9 4 3 3 1 6 9 8 6 8 12

output:

 35 6 1 1 2 1 2 2 3 2 3 3 3 4

There was such an attempt

 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); } }

Where appends() counts the number of calls (that is, the number of steps) and attributes to path (y+1) + " " + (x+1)

In simple examples, everything works, but there are such tests (which I do not know in advance) in which the code does not respond correctly, where and in what could be the error? or how best to complete this task?

  • I solved a problem similar to yours here , there I built the shortest path along the matrix. - tym32167

1 answer 1

Played with your task a little

Initial data:

 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];

teblitsa preparation

 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];

filling the table

 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];

build the way

 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)); }

conclusion

 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}");

Result

 35 6 1 1 2 1 2 2 3 2 3 3 3 4
  • Hehe, +, and I was too smart;) - MBo
  • @MBo I just solved this problem in the last few months 10 probably :) - tym32167