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
1d
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 SPRINKLR Production Analyst interview questions & answers
Popular interview questions of Production Analyst
Top HR questions asked in SPRINKLR Production Analyst
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