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++

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 |
#include <iostream> #include <cstring> using namespace std; #define N 4 // Check if cell (x, y) is valid or not bool isValidCell(int x, int y) { if (x < 0 || y < 0 || x >= N || y >= N) return false; return true; } void countPaths(int maze[N][N], int x, int y, int visited[N][N], int& count) { // if destination (bottom-rightmost cell) is found, // increment the path count if (x == N - 1 && y == N - 1) { count++; return; } // mark current cell as visited visited[x][y] = 1; // if current cell is a valid and open cell, if (isValidCell(x, y) && maze[x][y]) { // go down (x, y) --> (x + 1, y) if (x + 1 < N && !visited[x + 1][y]) countPaths(maze, x + 1, y, visited, count); // go up (x, y) --> (x - 1, y) if (x - 1 >= 0 && !visited[x - 1][y]) countPaths(maze, x - 1, y, visited, count); // go right (x, y) --> (x, y + 1) if (y + 1 < N && !visited[x][y + 1]) countPaths(maze, x, y + 1, visited, count); // go left (x, y) --> (x, y - 1) if (y - 1 >= 0 && !visited[x][y - 1]) countPaths(maze, x, y - 1, visited, count); } // backtrack from current cell and remove it from current path visited[x][y] = 0; } int main() { int maze[N][N] = { { 1, 1, 1, 1 }, { 1, 1, 0, 1 }, { 0, 1, 0, 1 }, { 1, 1, 1, 1 } }; // stores number of unique paths from source to destination int count = 0; // 2D matrix to keep track of cells involved in current path int visited[N][N]; memset(visited, 0, sizeof visited); // start from source cell (0, 0) countPaths(maze, 0, 0, visited, count); cout << "Total number of unique paths are " << count; return 0; } |

## Java

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 |
import java.util.Arrays; class Combinations { private static final int N = 4; // Check if cell (x, y) is valid or not private static boolean isValidCell(int x, int y) { if (x < 0 || y < 0 || x >= N || y >= N) return false; return true; } private static int countPaths(int maze[][], int x, int y, boolean visited[][], int count) { // if destination (bottom-rightmost cell) is found, // increment the path count if (x == N - 1 && y == N - 1) { count++; return count; } // mark current cell as visited visited[x][y] = true; // if current cell is a valid and open cell if (isValidCell(x, y) && maze[x][y] == 1) { // go down (x, y) --> (x + 1, y) if (x + 1 < N && !visited[x + 1][y]) count = countPaths(maze, x + 1, y, visited, count); // go up (x, y) --> (x - 1, y) if (x - 1 >= 0 && !visited[x - 1][y]) count = countPaths(maze, x - 1, y, visited, count); // go right (x, y) --> (x, y + 1) if (y + 1 < N && !visited[x][y + 1]) count = countPaths(maze, x, y + 1, visited, count); // go left (x, y) --> (x, y - 1) if (y - 1 >= 0 && !visited[x][y - 1]) count = countPaths(maze, x, y - 1, visited, count); } // backtrack from current cell and remove it from current path visited[x][y] = false; return count; } public static void main(String[] args) { int maze[][] = { { 1, 1, 1, 1 }, { 1, 1, 0, 1 }, { 0, 1, 0, 1 }, { 1, 1, 1, 1 } }; // stores number of unique paths from source to destination int count = 0; // 2D matrix to keep track of cells involved in current path boolean[][] visited = new boolean[N][N]; // start from source cell (0, 0) count = countPaths(maze, 0, 0, visited, count); System.out.println("Total number of unique paths are " + count); } } |

`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 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

If we changed the question to –

1.we can move only on prime numbers.

2.print longest path in lexicographically such that x1>x2 or x1=x2 then y2 > y1 for the order.

Here is my code please tell me what I am doing wrong-

http://ideone.com/VzWINK

Thanks in Advance!

Hi Jack,

Apologies for delayed response. We have edited your code and this seems to be working fine,

http://ideone.com/gu5EJF

There was problem with your

checkPrimeNumber()function. Also, not sure why you have modified visited array. We have restored the original code.Can we use dynamic programming for calculating the total number of unique paths? As the problem satisfy both optimal substructure and overlapping subproblem.

Thanks in advance..

Thanks for bringing this up. You’re right. If the matrix size if large, we can use dynamic programming.