Find total number of unique paths in a maze from source to destination

Find the total number of unique paths which the robot can take in a given maze to reach the destination from given source.


Positions in the maze will either be open or blocked with an obstacle. The robot can only move to positions without obstacles i.e. solution should find paths which contain only cells which are open. Retracing the 1 or more cells back and forth is not considered a new path. The set of all cells covered in a single path should be unique from other paths. At any given moment, the robot can only move 1 step in one of 4 directions. Valid moves are:

Go North: (x, y) –> (x – 1, y)
Go West: (x, y) –> (x, y – 1)
Go South: (x, y) –> (x + 1, y)
Go East: (x, y) –> (x, y + 1)

For example, consider below maze in the form of a binary matrix where 0 represents an blocked cell and 1 represents an open cell.

[ 1 1 1 1 ]
[ 1 1 0 1 ]
[ 0 1 0 1 ]
[ 1 1 1 1 ]

We have to find number of unique paths from source to destination. Above maze contains 4 unique paths (marked in blue color)

[ 1 1 1 1 ]      [ 1 1 1 1 ]      [ 1 1 1 1 ]      [ 1 1 1 1 ]
[ 1 1 0 1 ]      [ 1 1 0 1 ]      [ 1 1 0 1 ]      [ 1 1 0 1 ]
[ 0 1 0 1 ]      [ 0 1 0 1 ]      [ 0 1 0 1 ]      [ 0 1 0 1 ]
[ 1 1 1 1 ]      [ 1 1 1 1 ]      [ 1 1 1 1 ]      [ 1 1 1 1 ]


The robot should search for a path from the starting position to the goal position until it finds one or until it exhausts all possibilities. 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 unique path count 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:
Total number of unique paths are 4
 

Exercise: Extend the solution to print the paths as well
 

References:
https://www.cs.bu.edu/teaching/alg/maze/

 
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
wpDiscuz