Count all possible paths in maze

Tags: , ,

Count all possible paths in maze

Count all possible path in maze is one more grid problem which is asked in Amazon and Microsoft interviews and can be solved using dynamic programming. Before going into details of solution, let’s understand the problem. Problem statement is find total number of paths in a given maze or grid to reach at right most bottom cell from leftmost top cell. You can move right, down and diagonally and not left. For example, one of the path to reach bottom most cell is shown below

all possible paths in grid
One possible path to reach to destination

All possible paths in grid : Recursive approach

Typical property of a maze problem is that it reduces to a smaller problem as soon as we make one move. Another problem which uses the ame concept is Minimum cost path in grid . In any problem, once move is made, solve for smaller subproblem, in this case, try to figure out how many paths are possible from that new cell to destination cell. Also once we have decided to move in a particular direction (let’s say right) from a cell, that does not mean we need not count paths possible by going to other directions (down and diagonal). Hence for each cell, we have to count possible path if  we move right, possible paths if we move down and possible paths if we move diagonally and add them up.

Since, problem reduces to smaller problem with each move, think of applying recursion. What will be the base case for recursion?
Base will be when we reach at rightmost bottom cell. If we take i and j as row and column of maze, base case would be

(i == m && j ==n) return 1

Recursion formulation for maze problem would be

    count(i,j) =  count(i-1, j) + count(i, j-1) + count(i-1, j-1)

Recursive implementation would be

#include <stdio.h>

int PossiblePaths(int i,int j, int m, int n){
	if(i > m || j > n) return 0; 
	
	if(i == m && j == n) return 1;
	
	return PossiblePaths(i+1,j, m,n) 
			+ PossiblePaths(i, j+1, m,n) 
			+ PossiblePaths(i+1, j+1,m,n);
}

int main(void) {
	
	int m = 4;
	int n = 4;
	printf("\n Number of paths in maze : %d",PossiblePaths(0,0,m,n) );
	return 0;
}

Let’s see how the execution happens. We take a 3×3 maze so m and n equal to 3. To start with we take i and j  equal to 0.

all possible paths in a grid

Execution of above recursive implementation. From above figure, see that there are some subproblems which are calculated again and again. These will increase as we go down the tree.
Two basic conditions those should satisfy before we apply dynamic programming:

1. There should be optimal subproblem, which reduce original problem to smaller one and solving smaller problems lead to solution of bigger problem.
2. There should be overlapping subproblems which asks for tabulation of the results from subproblems to be used for solution further.

All possible paths in grid : DP implementation

To store solutions of subproblems, we would use two dimensional table.
Each cell Table(i,j) will store number of paths which are possible to reach cell(i,j). Our answer will be table(m,n).
Cell (i,j) can be reached at by either coming from (i-1,j) (Moving down) or by coming from cell (i,j-1) (Moving right) or by coming from cell (i-1, j-1) (Moving diagonally).

So our Table(i,j) can be calculated as Table(i,j) = Table(i-1,j) + Table(i,j-1) + table(i-1,j-1)
Also, to reach any cell in first column is 1 and cell in first row is also 1. Hence, Table(i,0) = Table(0,j) = 1

#include<stdlib.h>
#include<stdio.h>

int PossiblePaths(int m,int n){
	int Table[m+1][n+1];
	int i,j;
	
	for(i=0;i<=m; i++){
		Table[i][0] =1;
	}
	for(i=0;i<=n; i++){
		Table[0][i] =1;
	}
	for(i=1; i<=m; i++ ){
		for(j=1; j<=n; j++){
			Table[i][j] = Table[i-1][j] + Table[i][j-1] + Table[i-1][j-1];
		}
	}
	return Table[m][n];
}

int main(){
   printf("%d",PossiblePaths(4,4));
   return 0;
}

Space optimized version (Thanks to Jakube).

#include<stdlib.h>
#include<stdio.h>
 
int PossiblePaths(int m,int n){
	int Table[n+1];
	int diagonalSum = 0;
 
	for(int i=0;i<=n; i++){
		Table[i] = 1;
	}
	for(int i=1; i<=m; i++ ){
		int diagonalSum = 1;
		for(int j=1; j<=n; j++){
			int temp = Table[j];
			Table[j] = Table[j] +  Table[j-1] +  diagonalSum;
			diagonalSum = temp;
		}
	}
	return Table[n];
}
 
int main(){
   printf("%d",PossiblePaths(4,4));
   return 0;
}

Dynamic programming approach to find all possible paths in a grid takes extra O(N2) memory but reduces exponential time complexity to O(N2).

Please share if there is something wrong or missing, we would love to hear for you. If you want to contribute to website, please reach out to us on communications@algorithmsandme.com