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.
AnswerBot
4mo

Find the minimum cost to reach a destination in a matrix with blocked cells.

  • Use Breadth First Search (BFS) algorithm to explore all possible paths from the starting point to the destination.

  • Keep track...read more

Help your peers!
Select
Add answer anonymously...

Oyo Rooms Software Developer interview questions & answers

A Software Developer was asked Q. Given the head of a singly linked list and two integers m and n, reverse the nod...read more
A Software Developer was asked Q. Merge sort algorithm and divide array in the chunks
A Software Developer was asked Q. Position of Right Most Set Bit Determine the position of the rightmost set bit i...read more

Popular interview questions of Software Developer

A Software Developer was asked Q1. Given the head of a singly linked list and two integers m and n, reverse the nod...read more
A Software Developer was asked Q2. Merge sort algorithm and divide array in the chunks
A Software Developer was asked Q3. Position of Right Most Set Bit Determine the position of the rightmost set bit i...read more
Oyo Rooms Software Developer Interview Questions
Stay ahead in your career. Get AmbitionBox app
play-icon
play-icon
qr-code
Trusted by over 1.5 Crore job seekers to find their right fit company
80 L+

Reviews

10L+

Interviews

4 Cr+

Salaries

1.5 Cr+

Users

Contribute to help millions

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

Follow Us
  • Youtube
  • Instagram
  • LinkedIn
  • Facebook
  • Twitter
Profile Image
Hello, Guest
AmbitionBox Employee Choice Awards 2025
Winners announced!
awards-icon
Contribute to help millions!
Write a review
Write a review
Share interview
Share interview
Contribute salary
Contribute salary
Add office photos
Add office photos
Add office benefits
Add office benefits