How to Find the Shortest Path in a Binary Maze

In this problem we are given a binary matrix of size m-by-n. The matrix contains only 1s and 0s. The 1s in the matrix represent the path, and the 0s are the dead cells. We will be given two cell addresses. Our task is to find the shortest distance needed to go to the destination cell from the source cell. Let us see an example to understand the problem.

Input:

Output:

 The shortest path is 14 

Approach - 1

In this approach, we will perform DFS, and using backtracking, we will find the shortest path between the source and the destination cells.

Here are the steps we will follow:

• We will start from the given source cell address and continue exploring the paths in all four directions.
• We will continue until we reach the destination. In this way we will check out of those four directions, from which directions we can reach the destination cell.
• Then, through backtracking, we will calculate the path length. We will keep track of the path visited to avoid a loop.
• At last, we will return the shortest path length possible.

Code

Output:

 The shortest path length is 14 

Time Complexity: The time complexity of this approach is O(4 ^ M*N), where M and N are the dimensions of the matrix.

Space Complexity: We have used a matrix to store the visited array; hence, the space complexity of this approach is O(M * N).

Approach - 2

In this approach, we will use the Breadth First Search algorithm to solve the problem. For the BFS, we will use the queue data structure. The queue will store two things for each node. The first thing is the coordinates of the cell, and the second thing is the distance of this cell from the source cell. The main idea of using the BFS algorithm is that, unlike the DFS algorithm, the BFS algorithm takes all paths at once. Hence, it will move one cell forward in each path. The path through which the destination cell will be reached for the first time will be the shortest path. And since we are storing the distance of the cell from the source cell in the queue, we will get the path length, too.

Here is the algorithm of this approach.

• This time, we will start from the source cell.
• We will add the current cell in the node as well as its distance from the source cell.
• We will also create an array to keep track of the nodes visited.
• Then, we will loop the queue until it is empty.
• In the loop, we will take the first element of the queue and check if it is the same as the destination cell.
• If the destination cell is not reached, then we will move forward in all the possible directions.

Code

Output:

 The shortest path length is 14