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:
For more clarity of the question, watch this part of the video.
APPROACH :
Moving On:
In this problem we need to find all the paths which use a minimum number of counts.
So to solve this problem, first of all we need to build a 2D array dp, of size (n x m) and then start filling it from the bottom right cell. After that we will reverse engineer the dp using BFS (Breadth First Search).
Let's consider an example to understand the steps.
To fill the dp, we will use the same trick which we used to find the cost in Minimum Cost In Maze Traversal.
For any doubt regarding how to fill the dp matrix, it is advised that you check out the video lecture of minimum cost in maze traversal. You can also check this this part of the current problem's video lecture.
After getting the dp ready, the minimum count will be stored at the leftmost top cell in dp, which is 20 in this case.
Now, using a queue we will reverse engineer the dp matrix from top left (20) to 1 (bottom right) and find the path(s) by applying the BFS.
The steps to use BFS here would be:
First of all remove from the queue.
After that do some work i.e. compare the values present at a move of one step right (H) at dp[i][j+1] and at a move of one step down (V) at dp[i+1][j]. The one with smaller value is then added to the queue.
Rules:
So while adding an element from dp to queue, we also need to keep track of that element's position. So for that reason we put i (row) and j (column) corresponding to the element, along with the element in a pair and then add it to the queue.
Simultaneously we also need to maintain a string psf (path so far), so that we can keep track of the movements. To do so we can also put a string in the pair.
At any element n1 in the dp array, we have 2 options and that are, we can either take a horizontal move rightwards (H) or a vertical move downwards (V). We append a 'H' if we move right, otherwise append a 'V' if we move down at the end of the string of the removed pair and put it in the current pair.
In this case have 20 in the top left cell of the dp matrix. And i = 0 and j = 0 for 20. Therefore, we add this information in a pair and then push the pair in the queue.
After that we do some work corresponding to 20; we compare the values at dp[0][1] (18) and dp[1][0] (21), and add a pair corresponding to smaller value (18; i = 0, j = 1, 'H') in the queue.
Then we remove a pair (18, 0, 1, 'H') from the queue. After that we do some work corresponding to 18; we compare the values at dp[0][2] (12) and dp[1][1] (12). But both the values are similar, therefore we need to add two pairs corresponding to both of them (12; i = 0, j = 2, 'HH') and (12; i = 1, j = 1, 'HV') in the queue.
Then we remove a pair (12, 0, 2, 'HH') from the queue. After that we do some work corresponding to 12; we compare the values at dp[0][3] (11) and dp[1][2] (11). But both the values are similar, therefore we need to add two pairs corresponding to both of them (11; i = 0, j = 3, 'HHH') and (11; i = 1, j = 2, 'HHV') in the queue.
Again we remove a pair (12, 1, 1, 'HV') from the queue. After that we do some work corresponding to 12; we compare the values at dp[1][2] (11) and dp[2][1] (16), and add a pair corresponding to smaller value (11; i = 1, j = 2, 'HVH') in the queue.
Again we remove a pair (11, 0, 3, 'HHH') from the queue. After that we do some work corresponding to 11; we compare the values at dp[0][4] (16) and dp[1][3] (10), and add a pair corresponding to smaller value (10; i = 1, j = 3, 'HHHV') in the queue.
Again we remove a pair (11, 1, 2, 'HHV') from the queue. After that we do some work corresponding to 11; we compare the values at dp[1][3] (10) and dp[2][2] (11), and add a pair corresponding to smaller value (10; i = 1, j = 3, 'HHVH') in the queue.
Again we remove a pair (11, 1, 2, 'HVH') from the queue. After that we do some work corresponding to 11; we compare the values at dp[1][3] (10) and dp[2][2] (11), and add a pair corresponding to smaller value (10; i = 1, j = 1, 'HVHH') in the queue.
At this moment, there are 3 pairs in the queue; (10; i = 1, j = 3, 'HHHV'), (10; i = 1, j = 3, 'HHVH') and (10; i = 1, j = 3, 'HVHH'); which correspond to one single cell.
From here onwards whatever the path will be it will be same for all three. Here we have talked about the path corresponding to the first pair as that will be removed first.
Again we remove a pair (10, 1, 3, 'HHHV') from the queue. After that we do some work corresponding to 10; we compare the values at dp[1][4] (13) and dp[2][3] (10), and add a pair corresponding to smaller value (10; i = 2, j = 3, 'HHHVV') in the queue.
Again we remove a pair (10, 2, 3, 'HHHVV') from the queue. After that we do some work corresponding to 10; we compare the values at dp[2][4] (8) and dp[3][3] (9), and add a pair corresponding to smaller value (8; i = 2, j = 4, 'HHHVVH') in the queue.
Again we remove a pair (8, 2, 4, 'HHHVVH') from the queue. After that we do some work corresponding to 8; in this case we don't have the choice to move one step right as we are in the rightmost column. So we move to the only option available that is down move at dp[3][4] (8). And a pair corresponding to this (8; i = 3, j = 4, 'HHHVVHV').
Again we remove a pair (8, 3, 4) from the queue. After that we do some work corresponding to 8; in this case also we don't have the choice to move one step right as we are in the rightmost column. So we move to the only option available that is down move at dp[4][4] (1). And a pair corresponding to this (1; i = 4, j = 4, 'HHHVVHVV').
As i and j hit the limits so we print the psf.
Simultaneously work gets done for (10, 1, 3, 'HHVH') and (10, 1, 3, 'HVHH'); by following the same path, giving us the (1; i = 4, j = 4, 'HHVHVHVV') and (1; i = 4, j = 4, 'HVHVVHVV') respectively.
And as the base case has hit, their psf will also be printed.
For more clarity of this part; watch this part of the video.
Let's try to code this!
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.
A nested for loop is used 2 times, which condenses to O(n^2).
Space Complexity:
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.