Find Shortest Path in Maze

Given a maze in the form of the binary rectangular matrix, find length of the shortest path in maze from given source to given destination. The path can only be constructed out of cells having value 1 and at any given moment, we can only move one step in one of the four directions.


The Valid moves are:

Go Up: (x, y) –> (x – 1, y)
Go Left: (x, y) –> (x, y – 1)
Go Down: (x, y) –> (x + 1, y)
Go Right: (x, y) –> (x, y + 1)

For example, consider below binary matrix. If source = (0, 0) and destination = (7, 5), the shortest path from source to destination has length 12.

  shortest path


 
To find shortest path in 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 given source cell in the matrix and explore all four paths possible and recursively check if they will leads to the destination or not. We update the minimum path length whenever destination cell is reached. If a path doesn’t reach 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 current path in an matrix and before exploring any cell, we ignore the cell if it is already covered in current path.

 
C++ implementation –
 

Download   Run Code

Output:

The shortest path from source to destination has length 12

 
The time complexity of above backtracking solution will be higher since all paths need to be traveled. However, since it is an shortest path problem, BFS would be an ideal choice. If we use BFS to solve this problem, we travel level by level, so the first occurrence of the destination node gives us the result and we can stop our search there. The BFS approach is discussed here.

 
Thanks for reading.




Please use ideone or C++ Shell or any other online compiler link to post code in comments.
Like us? Please spread the word and help us grow. Happy coding 🙂
 





Leave a Reply

Notify of
avatar
Sort by:   newest | oldest | most voted
arks
Guest
arks

thanks for the excellent explanation

AllergicToBitches
Guest
AllergicToBitches
wpDiscuz