# Counting paths on grid

Given a maze as shown in figure below, **find count of all paths in maze** to reach at right most bottom cell from leftmost top cell. You can move right, down and diagonally and not left.This problem is called as “Counting paths on grid”. We will solve this problem using recursion and dynamic programming both.

To understand basic principles of dynamic programming, please refer: Dynamic Programming basics

Best thing about **Maze/Grid problems** is that they reduce to smaller problem as soon as we make one move from current position. For example in this problem, after making one move, problem reduces as how many paths are possible from new cell to destination cell. Add 1 to solution of this subproblem and you have solution to original problem.

However, in counting paths on grid problem, we can move in three direction. Once we move in a particular direction (let’s say right) from a cell, that does not mean that all paths possible by going to other directions (down and diagonal) should not be counted. Hence, for each cell, count possible path if move is made to right, possible paths if move was made to down and possible paths move was made diagonally and add them up.

## Counting paths on grid : Recursive approach

When solution to problem depends on solution to smaller problems, that usually hints towards recursion. As counting paths on grid problem reduces to smaller problem with each move, recursion is natural choice. For recursion to succeed, find is what is base case or terminating condition for the recursion condition? In *counting paths on grid problem,* base case will be when we reach destination cell (rightmost bottom cell). Let i and j be current row and column of the grid, base case would be

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

Recursion formulation for paths on grid problem would be

PossiblePaths(i,j,m,n) = PossiblePaths(i+1,j, m,n) // Move down + PossiblePaths(i, j+1, m,n) // Move right + PossiblePaths(i+1, j+1,m,n); // Move diagonally

### Counting paths on grid : Recursive implementation

#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; }

## Count paths on grid : dynamic programming

Let’s see what happens in execution of recursive implementation. Size of maze is 3×3, m and n equal to 3. To start i and j equal to 0.

From execution tree of recursive execution, it is evident that there are subproblems which are calculated multiple times. Number of such subproblems increases as size of maze increases and tree gets bigger. We know that there are two basic conditions that a problem must satisfy before dynamic programming can be applied to it.

1. There should be optimal subproblem, which reduce original problem to smaller subproblem.

2. There should be overlapping subproblems which asks for tabulation of the results from subproblems, to be used for solution of bigger problems.

With counting paths in maze problem, both conditions to apply DP are met.

To store results of subproblems, create a two dimensional, Table with dimensions same as maze.Table[i][j] stores number of paths possible to reach Maze[i][j]. Answer will Table[m][n].

Table (i,j) can be reached at by either coming from Table(i-1,j) (Moving down) or by coming from Table(i,j-1) (Moving right) or by coming from Table (i-1, j-1) (Moving diagonally).

Table[i][j] is calculated as:

Table(i,j) = Table(i-1,j) + Table(i,j-1)+ Table(i-1,j-1) Table[i][0] = Table[0][j] = 1

### Counting paths on grid : dynamic programming implementation

#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; }

Problem with above implementation is it uses m*n space. This can be optimized by storing only row at a time instead of entire table. Why? Because from the equation to calculate Table[i][j], we can see that it it only depends on previous row. Space optimized version (Thanks to Jakube for suggesting it )

#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; }

Finding all paths in a maze using dynamic programming takes extra O(n^{2})memory but reduces exponential time complexity to O(n^{2}).

Please share if you find something wrong or missing. If you want to contribute to site, please refer Publish on Algorithms and Me and contact us. We would be happy to publish your work and in turn will pay you too.

Pingback: Find Minimum Cost Path in a 2D Matrix: DP – Algorithms and Me()