Redirecting to
NADOS

Min Cost In Maze Traversal

  Prev   Next

Try First, Check Solution later

1. You should first read the question and watch the question video.
2. Think of a solution approach, then try and submit the question on editor tab.
3. We strongly advise you to watch the solution video for prescribed approach.

1. You are given a number n, representing the number of rows.
2. You are given a number m, representing the number of columns.
3. You are given n*m numbers, representing elements of 2d array a, which represents a maze.
4. You are standing in top-left cell and are required to move to bottom-right cell.
5. You are allowed to move 1 cell right (h move) or 1 cell down (v move) in 1 motion.
6. Each cell has a value that will have to be paid to enter that cell (even for the top-left and bottom- 
     right cell).
7. You are required to traverse through the matrix and print the cost of path which is least costly.
Input Format 
A number n
A number m
e11
e12..
e21
e22..
.. n * m number of elements
Output Format 
The cost of least costly path.
Question Video
Constraints 
1 <= n <= 10^2
1 <= m <= 10^2
0 <= e1, e2, .. n * m elements <= 1000
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


  • Editorial

    Let us say the position of the current cell is (i, j) then

    Moving 1 cell right will lead us to (i, j + 1)th cell

    Moving 1 cell down will lead us to (i + 1, j)th cell

    Let cost(i,j) represent the cost at (i,j)th cell and min_cost(i, j) represent the minimum cost to reach destination from the (i,j)th cell.

    From (i,j)th cell we can move to either (i, j+1) or (i+1, j)

    Now to reach the destination with minimum cost we will move in such a direction which will lead us to the destination with minimum cost as follows

    min_cost(i, j) = cost(i, j) + MIN{min_cost(i, j+1), min_cos{i+1, j}}

    DP tabulation:

    1.Create the dp table with same dimension as the given cost matrix

    2.dp[i][j] represent the minimum cost to reach destination from the (i,j)th cell

    Recursive equation in terms of dp table can be written as follows

    dp[i][j] = cost[i][j] + min(dp[i][j + 1], dp[i + 1][j])

    3.Base conditions:

    From any cell which belongs to the last row, we can move only in the right direction to reach the destination. ie.,

    dp[n-1][j] = cost[n-1][j] + dp[n-1][j+1]

    From any cell which belongs to the last column, we can move only in the down direction to reach destination i.e.,

    dp[i][m-1] = cost[i][m-1] + dp[i+1][m-1]

    Minimum cost to reach destination from (0, 0) is in dp[0][0]

    Example:

    Code:

    int min_cost(vector> &cost, int n, int m) {
                                    //Creating dp table
                                    vector
    > dp(n, vector
    (m, 0));
                                    
                                    dp[n-1][m-1] = cost[n-1][m-1];
                                    // Fill the last row
                                    for(int j = m-2; j >= 0; j--)
                                        dp[n-1][j] = cost[n-1][j] + dp[n-1][j+1];
                                     
                                    // Fill the last column  
                                    for(int i = n-2; i >= 0; i--)
                                        dp[i][m-1] = cost[i][m-1] + dp[i+1][m-1];
                                        
                                    // Fill the remaining cells
                                    for(int i = n-2; i >= 0; i--) {
                                        for(int j = m-2; j >= 0; j--) {
                                            dp[i][j] = cost[i][j] + min(dp[i+1][j], dp[i][j+1]);
                                        }
                                    }    
                                    return dp[0][0];
                                }

    java false

  • Asked in Companies
  • Related Topics






Video Solution

Code Solution

Run
 
Run
Id Name