New update is available. Click here to update.

Minimum Cost Path

MEDIUM

25 mins

26 upvotes

Matrices (2D Arrays)

Dynamic Programming

Solve problems & track your progress

Checkout your overall progress in every topic here

Become

Sensei

in DSA topics

Open the topic and solve more problems associated with it to improve your skills

Check out the skill meter for every topic

See how many problems you are left with to solve for cracking any stage. Score more than zero to get your progress counted.

Problem

Submissions

Minimum Cost Path

Contributed by

Anish De

Last Updated: 23 Feb, 2023

Medium

0/80

Avg time to solve 25 mins

Success Rate 70 %

26 upvotes

Problem Statement

You have been given a matrix of ‘N’ rows and ‘M’ columns filled up with integers. Find the minimum sum that can be obtained from a path which from cell (x,y) and ends at the top left corner (1,1).

From any cell in a row, we can move to the right, down or the down right diagonal cell. So from a particular cell (row, col), we can move to the following three cells:

Down: (row+1,col)
Right: (row, col+1)
Down right diagonal: (row+1, col+1)

Detailed explanation ( Input/output format, Notes, Images )

Input Format:

The first line will contain two integers ‘N’ and ‘M’ denoting the number of rows and columns, respectively.

Next ‘N’ lines contain ‘M’ space-separated integers each denoting the elements in the matrix.

The last line will contain two integers ‘x’ and ‘y’ denoting the cell to start from.

Output Format:

For each test case, print an integer that represents the minimum sum that can be obtained by traveling a path as described above.

Output for every test case will be printed in a separate line.

Note:

You don’t need to print anything; It has already been taken care of.

Constraints:

1 <= T <= 50
1 <= N, M <= 100
-10000 <= cost[i][j] <= 10000
1 <= x, y <= 100

Time limit: 1 sec

Sample Input 1:

Sample Output 1:

Explanation For sample input 1:

The minimum cost path will be (0, 0) -> (1, 1) -> (2, 3), So the path sum will be (3 + 1 + 8) = 12, which is the minimum of all possible paths.

Sample Input 2:

Sample Output 2:

Auto

Console