Shortest Path in a Binary Maze Problem Statement

Given a maze represented as a binary rectangular matrix of size M*N, where each element can either be 0 or 1, determine the length of the shortest path from a given source cell to a destination cell.

The path can only be traversed through a cell with a value of 1, and movement is possible in one of four directions at any moment. The valid moves are:

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 from the source to the destination exists, return -1.

Input:

The first line contains an integer ‘T’ representing the number of test cases.
For each test case:
The first line contains two integers M and N, representing the number of rows and columns.
The next M lines contain N integers each, representing the matrix.
The last second line contains two integers denoting the coordinates of the source.
The last line contains two integers denoting the coordinates of the destination.

Output:

For each test case, output a single integer representing the length of the shortest path from the source to the destination. If no path exists, output -1.

Example:

Input:

3 4
1 1 1 1
0 1 1 0
0 0 1 1
0 0
2 3

Output:

5

Explanation:

The binary matrix is 3 rows by 4 columns with a source at (0, 0) and a destination at (2, 3). The shortest path length is 5.

Constraints:

• 1 <= T <= 10
• 1 <= M, N <= 100
• Time Limit: 1 sec