Min cost Path

Moderate
0/80
5 upvotes
Asked in company
Microsoft

Problem statement

Given an integer matrix of size m*n, you need to find out the value of minimum cost to reach from the cell (0, 0) to (m-1, n-1).

From a cell (i, j), you can move in three directions : (i+1, j), (i, j+1) and (i+1, j+1).

Cost of a path is defined as the sum of values of each cell through which path passes.

Detailed explanation ( Input/output format, Notes, Images )
Input Format : 
Line 1 : Two integers, m and n
Next m lines : n integers of each row (separated by space)
Output Format : 
Minimum cost
Constraints :

1 <= m, n <= 100

Sample Input 1 :
3 4
3 4 1 2
2 1 8 9
4 7 8 1
Sample Output 1 :
13
Min cost Path
Full screen
Console