Shortest Path in a Binary Matrix Problem Statement

Given a binary matrix of size N * M where each element is either 0 or 1, find the shortest path from a source cell to a destination cell, consisting only of 1s. If no such path exists, return -1.

Note:
  • The matrix is 0-indexed.
  • You can move in 4 directions (up, down, left, right) from any cell.
  • The path length is the number of 1s on the path.
  • The source cell is always initialized as 1.

Example:

Input:
1 0 1
1 1 1
1 1 1
SOURCEX = 0, SOURCEY = 0, DESTX = 0, DESTY = 2
Output:
5
Explanation:

Several valid paths exist, such as:

X 0 X
X X X
1 1 1

Another valid path:

X 0 X
X 1 X
X X X

The shortest path from the source cell (0,0) to destination cell (0,2) consisting of 1s is of length 5.

Constraints:

  • 1 ≤ N ≤ 500
  • 1 ≤ M ≤ 500
  • MAT[i] = {0, 1}
  • 0 ≤ SOURCEX ≤ N - 1
  • 0 ≤ SOURCEY ≤ M - 1
  • 0 ≤ DESTX ≤ N - 1
  • 0 ≤ DESTY ≤ M - 1
  • MAT[SOURCEX][SOURCEY] = 1
  • Time Limit: 1 sec

Input:

The first line contains two integers 'N' and 'M', denoting the matrix dimensions.
Next 'N' lines contain 'M' space-separated integers, representing the matrix.
Following them, a line specifies 'SOURCEX' and 'SOURCEY'.
The final line specifies 'DESTX' and 'DESTY'.

Output:

A single integer representing the length of the shortest valid path from source to destination.
Note:
No need to print anything. Implement the function to solve the problem.
AnswerBot
4mo

Find the shortest path in a binary matrix from a source cell to a destination cell consisting only of 1s.

  • Use Breadth First Search (BFS) algorithm to find the shortest path.

  • Keep track of visited cells ...read more

Help your peers!
Select
Add answer anonymously...

Jupiter Money Software Developer interview questions & answers

A Software Developer was asked Q. Shortest Path in a Binary Matrix Problem Statement Given a binary matrix of size...read more
A Software Developer was asked Q. Can you explain how you would design a URL shortener?
A Software Developer was asked Q. Can you discuss a coding problem you encountered, your past projects, and any be...read more

Popular interview questions of Software Developer

A Software Developer was asked Q1. Design a Chess game using object-oriented principles.
A Software Developer was asked Q2. Shortest Path in a Binary Matrix Problem Statement Given a binary matrix of size...read more
A Software Developer was asked Q3. Can you explain how you would design a URL shortener?
Jupiter Money 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