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!
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


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
AmbitionBox Awards
Get AmbitionBox app

