Redirecting to
NADOS


  Prev   Next

Min cost In Maze Traversal







There are some things you learn best in calm, and some in storm.
~ Willa Cather

Min cost In Maze Traversal

Welcome coder to this question. Today we are going to discuss a very thought provoking problem "Minimum Cost in Maze Traversal". Are you ready? Let's begin.

Important Links : Question Video, Solution Video

You have already solved similar problems using the Recursive approach in the previous modules. You can refer to them in case you face any difficulties.

Have you read the problem statement? It's fairly simple. Let's catch you up on it or you can just watch the question video.

Problem Discussion :
  • You are given an array of dimensions n*m , representing elements of 2d array a, which represents a maze.
  • You are standing in the top-left cell and are required to move to the bottom-right cell.
  • You are allowed to move 1 cell right (h move) or 1 cell down (v move) in 1 move.
  • Each cell has a value that will have to be paid to enter that cell (even for the top-left and bottom-right cell).
  • You are required to traverse through the matrix upto the bottom-right most cell and print the cost of the path which is the least costly.

We understand this problem through the following input matrix:

img

Let's explore a path in this maze.

img

As you can see in figure 2, we can move either a step horizontally right or a step vertically down. So, if we move along the highlighted path, then the cost of traversal is 2+6+1+6+1+1+2+2+5+1+9+8+2= 46.

Many such paths exist; we need to find a path with minimum cost of traversal.

Approach :

Reader, you already know how we start such questions. We break the question in 3 parts: Storage & Meaning, Direction and Travel & Solve.

STORAGE & MEANING

It's fairly simple. We make an array for DP of the dimensions same as that of the maze i.e. n*m.

The meaning assigned to a single cell in this grid is that "to travel from that cell to the destination cell, what is the minimum cost to traverse out of all the paths".

DIRECTION

We always try to solve the question for a simpler and smaller problem via which we move on to the bigger problem.

We want you to meditate on the fact that to travel from the bottom right cell i.e. dp[n-1][m-1] to the the destination cell dp[n-1][m-1], the minimum cost of the path is the same as the cost of the cell corresponding to the input array (according to the "Meaning" we assigned for a single cell).

Why do you think it is so?

It's because we can't take a step in horizontal or vertical direction when we are already at the cell dp[n-1][m-1] and the maze comes to an end after that.

Hence our smaller problem lies at the bottom right or dp[n-1][m-1] cell. So we move from right to left direction in columns for every row from bottom to top while calculating the minimum cost.

img

Figure 3 is the DP array (drawn in green to differentiate from the input array) which denotes the direction of solving the dp array from bottom to top row.

TRAVERSE & SOLVE
img

In figure 4, we notice that the total cost to travel from source to destination via A,B and C is 200, 320 and 170. Hence, we take the route with the least cost i.e. path via C.

Reader, we apply the similar logic to our maze.

img

To find the minimum cost from B, we have only one choice to go horizontally right because we can't go vertically down as the maze comes to an end there.

Hence the minimum cost stored at B in the DP array is the sum of the original input array value at the cell B and the previous cell to its right i.e. 8+2=10.

BASE CASES :


Similarly, C, D, E, F and G have the only option to move a step horizontally as the maze comes to an end beyond that. Hence minimum cost at each cell is the sum of the original input value at that cell and cost at its previous cell to the right . Hence the DP array would look something like this:

img

Let's go through this traversal one more time.

img

We calculate the cost for the cell above '2' and it has only one option, to go in the vertical downwards direction. Hence its minimum cost is 9+2=11.

For cell X, we have 2 options, it can go horizontally right i.e. to 11 or vertically down i.e. to 10. Since 10< 11, therefore X chooses the vertical path and stores 0+10=10 in it.

Try to find the minimum costs for all the cells with this method and tally your result with ours.

img

Hence we find that to move from the source top left cell to the destination bottom right cell, the minimum cost is 36.

Have a look at the following code.

import java.io.*; import java.util.*; public class Main { 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++){ //1 for(int j=0;j< m;j++){ arr[i][j]=scn.nextInt(); } } int[][]dp=new int[n][m]; //2 for(int i=n-1;i>=0; i--){ //3 for(int j=m-1;j>=0;j--){ //4 if(i==n-1 && j==m-1){ //5 dp[i][j]=arr[i][j]; } else if(i==n-1){ //6 dp[i][j]=arr[i][j]+dp[i][j+1]; } else if(j==m-1){ //7 dp[i][j]=arr[i][j]+dp[i+1][j]; } else{ //8 int min=Math.min(dp[i+1][j],dp[i][j+1]); dp[i][j]=arr[i][j]+min; } } } System.out.println(dp[0][0]); //9 } }
java; true";
CODE DISCUSSION
  1. Array arr[n][m] is taken as the input for dimensions n and m.
  2. We make a new array dp[n][m] with the same dimensions as arr where each cell stores the minimum cost out of all the paths to travel from that cell to the destination cell dp[n-1][m-1].
  3. Since we start from the bottom row to the top row of the grid, therefore our loop runs from n-1 to 0th row.
  4. For every row, we start traversing from the rightmost column hence the column iteration runs from m-1 to 0.
  5. As we have already discussed in the "traversal" section, if we are at the destination cell then the minimum cost at that cell is the value of the input cell itself.
  6. If you are at the bottom row then there isn't an option of going vertically down. Hence, the value at the cell is the value of the input array added to the previous cell at the right.
  7. If one is at the last column then there isn't an option of going horizontally right available. Hence, the value at the cell is the value of the input array added to the previous cell below it.
  8. If it is neither of the above 2 cases, then the value at the cell is the sum of the value of input array and the minimum of vertical and horizontal costs.
  9. As already discussed, the minimum cost path out of all the possible paths is stored in dp[0][0]. This value is printed.
Analysis
Time Complexity :

O(n2)

This time complexity is quadratic because nested loops are used.

SPACE COMPLEXITY :

O(n2)

Since we use a 2D array for Dynamic Programming, therefore the space used is of complexity n2.

We encourage you to watch the video "Minimum Cost Path" for a clearer explanation of this problem.

With this we conclude our question "Minimum Cost Path". We'll bring you many such interesting questions as we move further along the lecture. So keep practicing Dynamic Programming with us!

Dynamic Programming
2D Arrays
Author: Arnab Sen
 
Run
Id Name