Print All Paths With Minimum Counts
We all have ability. The difference is how we use it.
~Charlotte Whitton
Welcome Back Reader!
In this article we will discuss about the next problem based on "Dynamic Programming" i.e. "Print All Paths with Minimum Counts".
Prerequisite for this problem is " Minimum Cost IN Maze Traversal".
Before you move any further, it is advised that you give this problem a fair try.
Let's jump to the problem.
Important Links : Problem Link, Solution Video
In this problem you are given two numbers n and m, representing the number of rows and the number of columns respectively. After that you are given n*m numbers, representing elements of 2d array a, which represents a maze.
Suppose that you are standing in the top-left cell and are required to move to the bottom-right cell and you are allowed to move 1 cell right (h move) or 1 cell down (v move) in 1 motion.
Each cell has a value that will have to be paid to enter that cell (even for the top-left and bottom-right cell).
All you are required to do is to traverse the matrix and print:
Sample Input:
6
6
0 1 4 2 8 2
4 3 6 5 0 4
1 2 4 1 4 6
2 0 7 3 2 2
3 1 5 9 2 4
2 7 0 8 5 1
Sample Output: 23
HVVHHVHVHV
HVVHHVHHVV
Path-1: HVVHHVHVHV -> 0 + 1 + 3 + 2 + 4 + 1 + 3 + 2 + 2 + 4 + 1 = 23
Path-2: HVVHHVHHVV -> 0 + 1 + 3 + 2 + 4 + 1 + 3 + 2 + 2 + 4 + 1 = 23
For more clarity of the question, watch this part of the video.
For more clarity of this part; watch this part of the video.
The above code snippet is used to fill the dp array. This is exactly the same as the code of the problem Minimum cost in Maze traversal.
Now to travel the dp matrix in order to find all the paths; we need a class pair to add the values and their coordinates to the queue. So in this pair class, we just put the i (row), j (column) and a string psf that stores the path so far. There is no need to store the value because we access it using i and j (dp[i][j]). And then we also create a constructor for this class.
//0 - Now we need a queue of type pairs and add a pair with psf as an empty string, I = 0 and j = 0. Then we apply a while loop which runs until the queue is empty. Then remove a pair from the queue.
//1 - First of all, we check if the pair corresponds to an element of the last cell, if yes then we print the psf of this pair.
//2 - After that we check if the pair corresponds to an element of the last column, if yes then create a new pair for the element which is one step down and put a string in this new pair by appending a 'V' in the psf of the previous pair and increment the i by 1 (as the last column means there is only option to move i.e. vertically downwards).
//3 - Then we check if the pair corresponds to an element of the last row, if yes then create a new pair for the element which is one step right and put a string in this new pair by appending a 'H' in the psf of the previous pair and increment the j by 1 (as the last row means there is only option to move i.e. horizontally right).
//4 - If the pair doesn't satisfy any of the conditions then the control comes to the else part. Entering the else part means there are two options available to the current pair's value. (one step right or one step down)
//4.1 - Then we check if the value present at one step right is smaller than the value at one step down from the value corresponding to the removed pair. If yes then create a new pair for the element which is one step right and put a string in this new pair by appending a 'H' in the psf of the previous pair and increment the j by 1.
//4.2 - Then we check if the value present at one step down is smaller than the value at one right from the value corresponding to the removed pair. If yes then create a new pair for the element which is one step down and put a string in this new pair by appending a 'V' in the psf of the previous pair and increment the i by 1.
//4.3 -If the pair doesn't satisfy any of the conditions then the control comes to the else part. Entering the else part means that the value at one step right and one step down is equal. So in this case we add 2 new pairs to the queue. One for the element which is one step down and put a string in this new pair by appending a 'V' in the psf of the previous pair and increment the i by 1.And another for the element which is one step right and put a string in this new pair by appending a 'H' in the psf of the previous pair and increment the j by 1.
For more clarity of the code, watch [14:35 - 28:24] part of the video.
java;
true";
O(n^2)
A nested for loop is used 2 times, which condenses to O(n^2).
O(n^2)
One n x n sized 2D array is used which condenses to O(n^2).
We hope that this article was helpful. If somehow you are finding it difficult to understand this problem then we advise you to watch our video lecture of this problem.
Trust me it will just get easier to understand after you have watched the solution video.
You can contact us via our website. Doubts, suggestions and feedback are always welcomed.
It is also advised that you follow the sequence of modules and questions which is there on our website.
Keep practicing more and more problems daily. Meditate enough on each step of each problem.
All the best for an exciting future!
Happy Coding!
