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
4d
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...
Top Jupiter Money Software Developer interview questions & answers
Popular interview questions of Software Developer
Top HR questions asked in Jupiter Money Software Developer
>
Jupiter Money Software Developer Interview Questions
Stay ahead in your career. Get AmbitionBox app
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
Get AmbitionBox app