Last Updated: 22 Nov, 2020
Shortest Path In A Binary Maze
Moderate
Asked in companies
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.
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:
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
Approaches
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.
The idea of an iterative approach is inspired from Lee algorithm that uses BFS (Breadth-first search). Below is the algorithm:
- Create an empty queue and enqueue source cell having distance 0 from source (itself) and mark it as visited.
- Loop till queue is empty
- Pop front node from the queue.
- If the popped node is the destination node, then return its distance.
- Else for each of 4 adjacent cells of the current cell, we enqueue each valid cell into the queue with +1 distance and mark them as visited.
- If all the nodes in the queue are processed, and the destination is not reached, then return -1.
BFS (Breadth-first search) works here because it doesn’t consider a single path at once. It considers all the paths starting from the source and moves ahead one unit in all those paths at the same time which makes sure that the first time when the destination is visited, it is the shortest path. So, the first occurrence of the destination cell gives us the result, and we can stop our search there. It is not possible that the shortest path exists from some other cell for which we haven’t reached the given node yet. If any such path was possible, we would have already explored it.
The idea of an iterative approach is to use level order traversal to get the level/distance of the destination cell. Below is the algorithm:
- Initialise the distance variable by 1.
- Create an empty queue, enqueue source cell and mark it as visited.
- Loop till queue is empty
- Traverse the current level, and for each node
- Pop front node from the queue.
- If the popped node is the destination node, then return current level/distance.
- Else for each of 4 adjacent cells of the current cell, we enqueue each valid cell into the queue and mark them as visited.
- Increment the distance variable by 1, as the destination cell is not present in the current level.
- Traverse the current level, and for each node
- If all the nodes in the queue are processed, and the destination is not reached, then return -1.
Level order traversal works here because it doesn’t consider a single path at once. It considers all the paths starting from the source and moves ahead one unit in all those paths at the same time which makes sure that the first time when the destination is visited, it is the shortest path. So, the first occurrence of the destination cell gives us the result, and we can stop our search there. It is not possible that the shortest path exists from some other cell for which we haven’t reached the given node yet. If any such path was possible, we would have already explored it.