# Min Cost In Maze Traversal

#### 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 nA number me11e12..e21e22.... n * m number of elements`
Output Format
`The cost of least costly path.`
Question Video
Constraints
`1 <= n <= 10^21 <= m <= 10^20 <= e1, e2, .. n * m elements <= 1000`
Sample Input
`660 1 4 2 8 24 3 6 5 0 41 2 4 1 4 62 0 7 3 2 23 1 5 9 2 42 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

• Related Topics

Run

Run
Id Name