Redirecting to
NADOS


  Prev   Next

Print all Paths with Maximum Gold







So much complexity in software comes from trying to make one thing do two things.
~Ryan Singer

Print all Paths with Maximum Gold

Welcome back, dear reader. So, how is it going? We hope that you are doing well. In this article, we will discuss the problem of PRINT ALL PATHS WITH MAXIMUM GOLD. So, what do we have to do in this question? Do you remember the GOLDMINE PROBLEM that we have solved in the foundation course? We recommend you refer to that problem first and also watch the Solution Video for the GOLDMINE PROBLEM as this question is just an extended version of the goldmine problem that you have already solved.

So, we will be given a 2-D matrix as shown in the figure below:


Important Links : Problem Link, Solution Video


img

Each cell in this matrix has an amount of gold present at it. We have to start digging from the 0th column and reach the last column and in the procedure, we can move either diagonally one step upward (called "d1") or one step forward in the same row (called "d2") or diagonally one step downward (called "d3") collecting the gold at the cell we reach. So, we have to find the paths with the maximum gold.

For instance, in the matrix shown above, the maximum gold that we can collect is 18 and there are 3 different paths to reach 18 as shown in the image below:

img

As you can see, the maximum amount of gold is 18. The first path is "2 d1 d2 d3". This means that we are starting from the 2nd row and the path is "d1 d2 d3". We have already discussed the meaning of "d1", "d2" and "d3". Why are we mentioning only the starting row and not the starting column in the paths? This is because we have already been told in the question that we have to start from the 0th column only.

So, dear reader, we hope that you have understood the problem completely. We suggest that you try to solve this problem first and then refer to the solution.

APPROACH :

Time Complexity: O(n x m) where n is the number of rows and m is the number of columns of the given input matrix.

Space Complexity: O(n x m)

Explanation:

So, dear reader, let us start first by finding out the maximum gold that we can collect, and then we will move to the method of printing all the paths that give us that maximum amount of gold.

  1. Storage and Meaning:
    We will make a 2-D matrix of the same size as that of the input matrix given to us. But, what will each element in the matrix store?
    img
    As shown in the image above, the element marked represents the maximum amount of gold that we can get if we start digging from that spot and reach the last column. So, this is what the meaning of each cell would be.
  2. Direction of Solving:
    The digging procedure is said to be complete only when we reach the last column. So, the smallest problem is when we are already at the last column.
    The largest/biggest problem is when we are in the first column. So, the direction of solving will be from the last column towards the first column.
    Also, the last column will have the same values like that in the last column of the input matrix. Why? Think about this!!!
    So, we have identified the direction of solving and we have also filled the last column already.
    img
    Note: Should we go from the 0th towards the last row or vice versa? The fact is that, whichever way you want to travel in the rows, you can. It will not affect our procedure or our answer. Why? Think about this!!!
  3. Travel and Solve:
    As discussed above, we have to start from the last column. Since the last column is already filled, let us start with the second last column. Also, we have discussed that we can start solving from any row. So, let us start from the 0th row itself i.e. let us move from top to bottom in the matrix.
    We are at dp[0][2]. The gold that we will collect at this spot is given in the input matrix. So, at least we will collect that gold. But, is this the maximum gold? No!!
    This is because we have not reached the last column yet. So, we have two ways to reach the last column.
    If we move "d2" the maximum gold that we can collect is the gold that we already have (by visiting dp[0][2] and i.e. arr[0][2]) plus the maximum gold that we get on reaching dp[0][3], So, if we move "d2", the maximum gold is 1+3=4.
    If we move "d3" the maximum gold that we can collect will be 3+0=3.
    So, the maximum out of these two options is 4. So, we will put 4 at dp[0][2].
    img
    So, now we reach dp[1][2]. This time, we will have three options and they are dp[0][3], dp[1][3] and dp[2][3]. The maximum out of these three is dp[2][3] i.e. 3. So, we will add 3, to the gold that we get at dp[1][2] i.e. our current position and we get 9.
    img
    So, this is the process that we will follow.

You have to remember these points when you fill the matrix:

  1. When we are in the first row, we have only two choices i.e. "d2" and "d3".
  2. When we are in the last row, we have only two choices i.e. "d1" and "d2".
  3. When we are not in these two rows, we will have three choices: "d1", "d2", and "d3".

Now, we request you complete the dp matrix yourself now. The complete matrix is shown below for your reference:

img

So, dear reader, we hope that you have understood the procedure till here. Now, it is the time we try to solve the second part of the question where we have to print all the paths that give us the maximum answer.

If you have any doubts regarding the procedure till here, refer to the solution video to understand this procedure in short or refer to the GOLDMINE SOLUTION VIDEO to understand the above procedure in detail.

Printing all the Maximum Gold Paths

Let us have a look at the dp matrix that we have just filled

img

Here, in the first column, we have 2 positions that have the maximum values. See, we have already found the maximum value from the first row as it was our answer to the first part of the question. Now, we will search in the first column and we will put a pair of all those positions that have the same value as the maximum value.

Here, we have the max gold value=18 at dp[2][0] and dp[3][0] respectively. So, we will make a pair class in the code that will have the location of this spot and the path so far. Since we have to initially mention the row number, in this first step, we will add the row number to the path so far. The queue will look as shown in the figure

img

So, the numerator in the above diagram shows the location where the max value is found and the denominator shows the path so far. We have also marked the elements in the matrix as well.

Now we will apply a repetitive algorithm. We will remove the element from the queue and we will check all the positions at which we can go to from it i.e. we will check for the moves "d1", "d2", and "d3". We will add those elements to the queue which gives us the maximum answer. Have a look at the diagram shown below:

img

So, we removed the first element from the queue, and the element that was after it is now at the front of the queue and we saw that when we are at dp[2][0] if we make a "d1" move then we get the maximum gold. So, we added a new element to the queue which specifies the location to which we have moved in our path (i.e. 1,1) and we added "d1" to the path so far.

Now, we will repeat the above procedure till the queue is not empty. See for the next turn for instance:

img

We remove the first element from the queue again and the next element came at the front. Now, we have two values that give us the maximum gold. So, we put both these values into the queue and the path so far was added with the path that we took to reach those two values.

Now, the first element of the queue is representing dp[1][1]. So, it will be removed and we will search in the available moves, the move that will give us the max gold. In this case, it will be when we reach dp[1][2]. So, the movie is "d2" and the path and the queue will be:

img

So, this process will continue till the queue is not empty and we will print the path when we reach the last column. Dear reader, we request you complete the remaining procedure yourself as it is very easy and also repetitive.

Just remove the element from the queue, go to that element and see what paths give you the maximum gold, and add all those paths to the queue.

We recommend you refer to the solution video to understand this procedure and the code based on this procedure that we have written below simultaneously. This will help you understand the code very easily and in-depth.

Now that we have understood the above procedure, let us write the code for the same.

import java.util.*; public class Main { private static class Pair { String psf; int i; int j; public Pair(String psf, int i, int j) { this.psf = psf; this.i = i; this.j = j; } } public static void main(String[] args) throws Exception { Scanner scn=new Scanner (System.in); int n=scn.nextInt(); int m=scn.nextInt(); int[][] arr = new int[n][m]; for (int i = 0; i < n; i++) { for (int j = 0; j < m; j++) { arr[i][j] = scn.nextInt(); } } scn.close(); int[][] dp = new int[arr.length][arr[0].length]; for(int j = arr[0].length - 1; j >= 0; j--){ for(int i = 0; i < arr.length; i++){ if(j == arr[0].length - 1){ dp[i][j] = arr[i][j]; } else if(i == 0){ dp[i][j] = arr[i][j] + Math.max(dp[i][j + 1], dp[i + 1][j + 1]); } else if(i == arr.length - 1){ dp[i][j] = arr[i][j] + Math.max(dp[i][j + 1], dp[i - 1][j + 1]); } else { dp[i][j] = arr[i][j] + Math.max(dp[i][j + 1], Math.max(dp[i - 1][j + 1], dp[i + 1][j + 1])); } } } int max = Integer.MIN_VALUE; for(int i = 0; i < dp.length; i++){ if(dp[i][0] > max){ max = dp[i][0]; } } System.out.println(max); ArrayDeque< Pair> que = new ArrayDeque< >(); for(int i = 0; i < dp.length; i++){ if(dp[i][0] == max){ que.add(new Pair(i + " ", i, 0)); } } while(que.size() > 0){ Pair rem = que.removeFirst(); if(rem.j == arr[0].length - 1){ System.out.println(rem.psf); } else if(rem.i == 0){ int g = Math.max(dp[rem.i][rem.j + 1], dp[rem.i + 1][rem.j + 1]); if(g == dp[rem.i][rem.j + 1]){ que.add(new Pair(rem.psf + "d2 ", rem.i, rem.j + 1)); } if(g == dp[rem.i + 1][rem.j + 1]){ que.add(new Pair(rem.psf + "d3 ", rem.i + 1, rem.j + 1)); } } else if(rem.i == arr.length - 1){ int g = Math.max(dp[rem.i][rem.j + 1], dp[rem.i - 1][rem.j + 1]); if(g == dp[rem.i - 1][rem.j + 1]){ que.add(new Pair(rem.psf + "d1 ", rem.i - 1, rem.j + 1)); } if(g == dp[rem.i][rem.j + 1]){ que.add(new Pair(rem.psf + "d2 ", rem.i, rem.j + 1)); } } else { int g = Math.max(dp[rem.i][rem.j + 1], Math.max(dp[rem.i - 1][rem.j + 1], dp[rem.i + 1][rem.j + 1])); if(g == dp[rem.i - 1][rem.j + 1]){ que.add(new Pair(rem.psf + "d1 ", rem.i - 1, rem.j + 1)); } if(g == dp[rem.i][rem.j + 1]){ que.add(new Pair(rem.psf + "d2 ", rem.i, rem.j + 1)); } if(g == dp[rem.i + 1][rem.j + 1]){ que.add(new Pair(rem.psf + "d3 ", rem.i + 1, rem.j + 1)); } } } } }
java; true";
Analysis
Time Complexity:

The time complexity of the above solution is O(n x m) as we are traversing in a matrix of size n x m.

Space Complexity:

The space complexity of the above solution is also O(n x m) as we have created a matrix of size n x m.

So, dear reader, we hope that you have understood the problem completely. We recommend you refer to the complete solution video to clear all your doubts if any. With this, we have completed this problem.

Suggestions:

Here are some suggestions from our side that you do not want to miss:

Did you notice anything? The procedure we did to print the paths is the BFS of a graph. We recommend you complete the foundation course once and then start solving problems in Level-2. This way, you will be able to understand the problems better as well as you will be able to solve more problems yourself otherwise it will be very difficult for you to come up with any solution. So, keep practicing and moving forward. Till then, happy coding!!!

Print all Paths with Maximum Gold
Dynamic Programming and Greedy
Author: Guneet Malhotra
 
Run
Id Name