Shortest Path In A Binary Maze

Moderate
0/80
Average time to solve is 30m
profile
Contributed by
25 upvotes
Asked in companies
SamsungAmazonHSBC

Problem statement

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

The path can only be created out of a cell if its value is 1 and at any given moment, we can only move one step in one of the four directions. 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 there is no path from a given source cell to a destination cell, return -1.

For example : 
consider the binary matrix below. If source = (0, 0) and destination = (3, 4), the shortest path from source to destination has length 11.

example

Detailed explanation ( Input/output format, Notes, Images )
Input Format : 
The first line of input contains an integer ‘T’ representing the number of test cases. Then the test cases follow.

The first line of each test case contains two space-separated integers M and N, representing the number of rows and columns respectively.

Each of the next M lines contains N space-separated integers representing the matrix.

The last second line of each test case contains two space-separated integers denoting the coordinates of the source cell.

The last line of each test case contains two space-separated integers denoting the coordinates of the destination cell.

For example, the input for the binary matrix depicted in the below image would be:

example

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

Explanation :

The first line represents that the given matrix has 3 rows and 4 columns.
Each of the next 3 lines contains 4 space-separated integers representing a row.
Last second line contains two space-separated integers representing coordinates of the source cell, i.e. (0, 0).
The last line contains two space-separated integers representing coordinates of the destination cell, i.e. (2, 3).
Output Format : 
For each test case, print a single integer denoting the length of the shortest path between a given source cell to a destination cell. If such a path does not exist, print -1.

The output for each test case is in a separate line.
Note : 
You do not need to print anything; it has already been taken care of. Just implement the given function.
Constraints : 
1 <= T <= 10
1 <= M, N <= 100

Time Limit: 1sec
Sample Input 1 :
2
3 4
1 1 1 1
0 1 1 0
0 0 1 1
0 0
2 3
2 2
1 1
0 1
0 0
1 1
Sample Output 1 :
5
2
Explanation of Sample Input 1 :
For the first test case, the shortest path between the source cell (0, 0) and destination cell (2,3) is highlighted in the figure below, having a length of 5.

example

For the second test case, the only path from the source cell to the destination cell has a length of 2.
Sample Input 2 :
2
2 2
1 1
1 1
0 1
1 1
2 2
1 0
0 1
0 0
1 1
Sample Output 2 :
1
-1
Hint

Consider all the possible paths from the source cell to the destination cell with the help of backtracking.

Approaches (3)
Naive Approach

To find the shortest path in a maze, we search for all possible paths in the maze from the starting position to the goal position until all possibilities are exhausted. We can easily achieve this with the help of backtracking. We start from a given source cell in the matrix and explore all four possible paths and recursively check if they will lead to the destination or not. We update the minimum path length whenever the destination cell is reached. If a path doesn’t reach its destination or we have explored all possible routes from the current cell, we backtrack. To make sure that the path is simple and doesn’t contain any cycles, we keep track of cells involved in the current path in a matrix and before exploring any cell, we ignore the cell if it is already covered in the current path.

Time Complexity

O(4 ^ (M * N)), where ‘M’ is the total number of rows in the maze and ‘N’ is the total number of columns in the maze.

 

The time complexity of a backtracking solution will be exponential since all paths need to be travelled.

Space Complexity

O(M * N), where ‘M’ is the total number of rows in the maze and ‘N’ is the total number of columns in the maze.

 

We are using O(H) extra space for the call stack where ‘H’ is the height of the recursion tree, and height of a recursion tree could be ‘M * N’ in the worst case. Thus, the final space complexity is O(M * N).

Code Solution
(100% EXP penalty)
Shortest Path In A Binary Maze
Full screen
Console