Minimum Cost to Destination

You are given an NxM matrix consisting of '0's and '1's. A '1' signifies that the cell is accessible, whereas a '0' indicates that the cell is blocked. Your task is to compute the minimum cost required to travel from the starting point (0, 0) to a specified destination (X, Y).

You can move in the following four directions from any given cell (i, j):

1. Left - (i, j-1)
2. Right - (i, j+1)
3. Up - (i-1, j)
4. Down - (i+1, j)

Traversing in the 'Up' and 'Down' directions incurs a cost of 1. Movements to the 'Left' and 'Right' are free of cost. If it is impossible to reach (X, Y), return -1.

Input:

The first line contains two integers 'N' and 'M', representing the number of rows and columns of the matrix, respectively.
The next N lines contain M integers each, representing the row values of the matrix.
The final line consists of two integers, 'X' and 'Y', denoting the destination coordinates.

Output:

Print the minimum cost to reach (X, Y) from (0, 0). If the destination is unreachable, print -1.

Example:

Input:
3 3
1 0 1
1 1 0
0 1 1
2 2
Output:
2

Constraints:

  • 1 <= N <= 10^3
  • 1 <= M <= 10^3
  • 0 <= matrix[i][j] <= 1
  • 0 <= X < N
  • 0 <= Y < M

Note:

  • The starting point matrix[0][0] will always be 1.
  • 'X' and 'Y' are 0-based indices.
  • You do not need to print the output, implement the function that computes the result.
Be the first one to answer
Add answer anonymously...
Oyo Rooms Software Developer 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