Recursively!! find cheapest path (minumum sum!!) through 2D array. the 2D array

Question

Recursively!! find cheapest path (minumum sum!!) through 2D array.

the 2D array is:

27 19 18 85 32 11 18 24 22 98
60 83 52 61 18 64 74 33 95 42
56 27 71 56 65 70 18 78 35 74
15 89 19 92 61 76 92 42 57 26
88 28 78 45 21 98 11 72 82 97
49 54 88 79 16 43 27 78 52 71
17 18 60 40 72 39 70 52 96 11
62 79 25 50 73 40 98 64 44 72
25 79 72 25 64 35 29 16 77 96
12 93 49 64 61 34 83 87 34 36

The text file provided is a 2D grid of integer values that represent a board. We would like to
compute the lowest cost to travel from the top row to bottom row. The cost is sum of all cells
visited from the top row to the bottom row as follows. Starting at a fixed value in the top row, we
will take consecutive jumps to lower rows under the restriction that each jump can be in the
same column, the column immediately to the left or the column immediately to the right of the
current column.
example:
Let the grid be:
27 19 18 85 32
60 83 52 61 18
56 27 71 56 65
15 89 19 92 61
88 28 78 45 21
So if we start at 18, then we have the option of jumping to either 52,
83 or 61. If we jump to 61, then from 61 we can jump to either 56, 71
or 65. So if we continue to jump to 65 then 92 and finally 78, then
the cost of the path is: 18 + 61 + 65 + 92 + 78 = 314.
What to do:
1) Write code that reads the text file provided and stores the values in a 10 x 10 2D array.
2) Write a recursive method that returns the cheapest path from a fixed starting point at the top
row. Therefore your method looks like:
int cheapestFromPoint(int[][] grid, int startingRow, int staringColumn)
Hint 1: The cheapest cost from a starting point (i, j) where i is row value and j is column value is
the value at grid[i][j] and the cheapest path through (i+1, j) or (i+1, j-1) or (i+1, j+1)
Hint 2: You may want to use the Math.min(int a, int b) that returns the minimum of two values.
How could we use that method to determine the minimum of three values?
3) Using the recursive method you created in (2), compute the cheapest cost from the top row to
the bottom row by using each cell at the top row as a starting point. You do not need to
compute the jumps (path), but only the cheapest cost.

Explanation / Answer

Answers for all above parts mentioned in the above question have described in the following code :

Related Questions

Navigate

• Browse (All)
• Browse R
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.