Code360 powered by Coding Ninjas X Naukri.com. Code360 powered by Coding Ninjas X Naukri.com

Minimum Cost Path

Moderate
0/80
Average time to solve is 25m
profile
Contributed by
31 upvotes
Asked in companies
Goldman SachsOlaSalesforce

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 )
Constraints:
1 <= T <= 50
1 <= N, M <= 100
-10000 <= cost[i][j] <= 10000
1 <= x, y <= 100

Time limit: 1 sec
Sample Input 1:
3 4
3 4 1 2
2 1 8 9
4 7 8 1
2 3
Sample Output 1:
12
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:
3 4
11 2 8 6 
2 12 17 6 
3 3 1 8 
3 4
Sample Output 2:
25
Full screen
Console