Advertisement
pifka

Move Down/Right

Sep 15th, 2019
153
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 2.40 KB | None | 0 0
  1. using System;
  2. using System.Collections.Generic;
  3. using System.Linq;
  4.  
  5. namespace ConsoleApp4
  6. {
  7. public class Program
  8. {
  9. public static void Main()
  10. {
  11. var rows = int.Parse(Console.ReadLine());
  12. var cols = int.Parse(Console.ReadLine());
  13.  
  14. var numbers = new int[rows, cols];
  15.  
  16. for (int i = 0; i < cols; i++)
  17. {
  18. var line = Console.ReadLine().Split();
  19.  
  20. for (int j = 0; j < cols; j++)
  21. {
  22. numbers[i, j] = int.Parse(line[j]);
  23. }
  24. }
  25.  
  26. var sums = new int[rows, cols];
  27.  
  28. sums[0, 0] = numbers[0, 0];
  29.  
  30. for (int row = 1; row < rows; row++)
  31. {
  32. sums[row, 0] = sums[row - 1, 0] + numbers[row, 0];
  33. }
  34.  
  35. for (int col = 1; col < cols; col++)
  36. {
  37. sums[0, col] = sums[0, col - 1] + numbers[0, col];
  38. }
  39.  
  40. for (int row = 1; row < rows; row++)
  41. {
  42. for (int col = 1; col < cols; col++)
  43. {
  44. var res = Math.Max(
  45. sums[row - 1, col],
  46. sums[row, col - 1])
  47. + numbers[row, col];
  48.  
  49. sums[row, col] = res;
  50. }
  51. }
  52.  
  53. var result = new Stack<string>();
  54.  
  55. result.Push($"[{rows - 1}, {cols - 1}]");
  56.  
  57. var currentRow = rows - 1;
  58. var currentCol = cols - 1;
  59.  
  60. while (currentRow != 0 || currentCol != 0)
  61. {
  62. var top = -1;
  63.  
  64. if (currentRow - 1 >= 0)
  65. {
  66. top = sums[currentRow - 1, currentCol];
  67. }
  68.  
  69. var left = -1;
  70.  
  71. if (currentCol - 1 >= 0)
  72. {
  73. left = sums[currentRow, currentCol - 1];
  74. }
  75.  
  76. if (top > left)
  77. {
  78. result.Push($"[{currentRow - 1}, {currentCol}]");
  79. currentRow -= 1;
  80. }
  81.  
  82. else
  83. {
  84. result.Push($"[{currentRow }, {currentCol - 1}]");
  85. currentCol -= 1;
  86. }
  87. }
  88.  
  89. Console.WriteLine(string.Join(" ", result));
  90. }
  91. }
  92. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement