Problem: Given a maze in the form of a binary rectangular matrix, we have to find the shortest path from the given source to the given destination. The path can only be created with the cells of 1.

It is important to note that only vertical and horizontal movements are allowed.

Shortest Path in Maze

We can easily find the shortest path in the maze by using the backtracking algorithm.

The idea is to keep moving through a valid path until stuck, otherwise backtrack to the last traversed cell and explore other possible paths to the destination.

For each cell, the following 4 moves are possible:

  • Up – (x, y-1)
  • Down – (x, y+1)
  • Right – (x+1, y)
  • Left – (x-1, y)

We validate every move before undertaking it. If any move is not valid, we check for the next one.

For example, if the upper cell is zero, we test for the lower cell. If the lower cell also contains zero, we check for the right cell. If the right cell is also not valid, we go for the left cell if it is valid.

If non of the 4 moves are valid, we backtrack to the last visited cell to choose another cell (path) so that we can avoid the current cell which doesn’t have any path to the destination.

On reaching the destination, we deliberately backtrack to explore other possible paths to the destination cell.

After exhausting all possibilities, we output the path with the minimum length.

Here is the recursive implementation of the solution using backtracking in C++, Java and Python:

Python

C++

Java

Output:

Shortest Path Length: 12

In the above program, the visit(int x, int y) is the recursive function implementing the backtracking algorithm.

The canVisit(int x, int y) function checks whether the current cell is valid or not. We use this function to validate the moves.

We are using the visited[][] array to avoid cyclic traversing of the path by marking the cell as visited.

We visit a cell of the maze matrix by updating the corresponding cell in the visited[][] matrix with the value of 1 i.e. visited[x][y]=1.

Every time we mark a cell as visited we also increment the length of the current path. by 1 i.e. length++.

We recursively traverse the next valid cell until we reach the destination cell.

On reaching the destination cell we update the minimum path length i.e. shortLength = min(shortLength, length).

In the driver code of our program, we are initiating the search process and outputting the shortest path of the maze (if it has any).

The backtracking process of finding the shortest path in the maze is not efficient because it explores all possible paths to the destination, which may not be the final solution.

In this programming tutorial, we learned to find the shortest path in the binary maze using the backtracking algorithm in Python, C++, and Java Programming languages.

Leave a Reply