
Shortest Path in a Binary Maze
Find the length of the shortest path in a binary maze given in the form of a rectangular matrix of size M*N, where each element is 0 or 1. Calculate the shortest path from a designated source cell to a destination cell if one exists.
Explanation:
The path can only be made if the cell value is 1, and movements can occur in the following four directions:
Up: (x, y) -> (x - 1, y)
Left: (x, y) -> (x, y - 1)
Down: (x, y) -> (x + 1, y)
Right: (x, y) -> (x, y + 1)
If no path exists from the source to the destination, return -1.
Input:
Integer T, the number of test cases.
For each test case:
- Two integers M and N, representing rows and columns.
- M lines with N space-separated integers, representing the matrix.
- One line with two integers, the source cell coordinates.
- One line with two integers, the destination cell coordinates.
Output:
For each test case, a single integer representing the shortest path's length, or -1 if no path exists.
Example:
Input:
1
3 4
1 1 1 1
0 1 1 0
0 0 1 1
0 0
2 3
Output:
5
Constraints:
- 1 <= T <= 10
- 1 <= M, N <= 100
Time Limit: 1 sec

AnswerBot
5d

Find the length of the shortest path in a binary maze from source to destination.
Use BFS algorithm to find the shortest path in the binary maze.
Create a visited matrix to keep track of visited cells.
C...read more

Help your peers!
Add answer anonymously...
Top Amazon Software Developer interview questions & answers
Popular interview questions of Software Developer
Top HR questions asked in Amazon Software Developer
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