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
Contributed by

## 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
``````
Console