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.

Below is C++/Java implementation of the idea –


Download   Run Code


Download   Run Code


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.

1 Star2 Stars3 Stars4 Stars5 Stars (4 votes, average: 5.00 out of 5)


Thanks for reading.

Please use our online compiler to post code in comments. To contribute, get in touch with us.
Like us? Please spread the word and help us grow. Happy coding 🙂

Leave a Reply

newest oldest most voted
Notify of

thanks for the excellent explanation


hello could you please share with this language c


What is time complexity of this solution?


We can think of this like a graph where the edges represent possible paths. run BFS to find the shortest path.