Minimum Cost Path Problem Statement

Given an N x M matrix filled with integers, determine the minimum sum obtainable from a path that starts at a specified cell (x, y) and ends at the top left corner of the matrix (1, 1).

Explanation:

You can move in the following directions from any cell:

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

Input:

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:

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. 

Example:

Input:
3 3
4 8 2
2 5 7
6 1 9
3 3
Output:
14
Explanation:

Starting from cell (3, 3), one minimum path is 9 → 1 → 2 → 2, thus the minimum sum is 14.

Constraints:

  • 1 <= T <= 50
  • 1 <= N, M <= 100
  • -10000 <= cost[i][j] <= 10000
  • 1 <= x, y <= 100
  • Time limit: 1 sec
Note:
You don’t need to print anything; It has already been taken care of.
Be the first one to answer
Add answer anonymously...
Cisco Consultant Engineer Interview Questions
Stay ahead in your career. Get AmbitionBox app
qr-code
Helping over 1 Crore job seekers every month in choosing their right fit company
65 L+

Reviews

4 L+

Interviews

4 Cr+

Salaries

1 Cr+

Users/Month

Contribute to help millions

Made with ❤️ in India. Trademarks belong to their respective owners. All rights reserved © 2024 Info Edge (India) Ltd.

Follow us
  • Youtube
  • Instagram
  • LinkedIn
  • Facebook
  • Twitter