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 76 77 |
#include <bits/stdc++.h> 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 (!visited[x + 1][y]) countPaths(maze, x + 1, y, visited, count); // go up (x, y) --> (x - 1, y) if (!visited[x - 1][y]) countPaths(maze, x - 1, y, visited, count); // go right (x, y) --> (x, y + 1) if (!visited[x][y + 1]) countPaths(maze, x, y + 1, visited, count); // go left (x, y) --> (x, y - 1) if (!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; } // main function 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]; // initalize visited[][] by 0 (unvisited) 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; } |

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

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.