Finding All Unique Paths From Top-Left To Bottom-Right Corner Problem Statement : Find the number of unique paths from source to destination in a grid, given conditions

• Your initial position is the top-left corner of the grid i.e grid [ 0 ] [ 0 ].
• Your destination is the bottom-right corner of the grid i.e grid [ r - 1 ] [ c - 1 ].
• One can only take a path to the right of the current cell or a path below the current cell.

The idea behind this algorithm is quite simple.

• For all the cells in the top-most row, there is only one path from the left to reach each of them as one cannot reach these cells from above.
• For all the cells in the left-most column, there is only one path from above to reach each of them as one cannot reach these cells from the left.
• For all the remaining cells at position [ r ] [ c ] one can reach from the left cell
i.e at postion [ r ] [ c - 1 ] or from the cell above at position [ r - 1 ] [ c ].

Recursive Algorithm : UniquePaths ( row, column )

1. If row < 0 or column < 0 then
[ As there cannot be any paths coming from the left of 0’th column
or any paths coming from the top of the 0’th row. ]
return 0
2. If row equals 0 or column equals 0 then
[ As there is only one path in the 0’th column
and only one path in the 0’th row. ]
return 1
3. For all the other cells that are not in the leftmost column and topmost row
return UniquePaths ( row - 1, column ) + UniquePaths ( row, column - 1 )

C++ Finding all unique paths in a grid using recursion

#include<iostream>

using namespace std;

int Unique_Paths (int row, int col) {

// If the row or column number is less than 0, i.e if we must
// have stepped beyond the grid so there is no path to be found.
if (row < 0 or col < 0)
return 0;

// There is only one path going through the topmost row and leftmost column
if (row == 0 || col == 0) {
return 1;
}

// For all the other cells not in topmost row and leftmost column
// The number of paths is the addtion of paths from the cell above and cell
// to the left of the current cell.
return Unique_Paths (row - 1, col) + Unique_Paths (row, col - 1);
}

int main() {

int rows = 7, cols = 3, paths;

paths = Unique_Paths(rows-1, cols-1);
cout << "Grid Rows : " << rows << " Columns : " << cols << " Paths : " << paths << endl;

rows = 3, cols = 3;

paths = Unique_Paths(rows-1, cols-1);
cout << "Grid Rows : " << rows << " Columns : " << cols << " Paths : " << paths << endl;

return 0;
}

Output

Grid Rows : 7 Columns : 3 Paths : 28
Grid Rows : 3 Columns : 3 Paths : 6

Dynamic Programming Algorithm : UniquePaths ( rows, cols )

1. Base Case : Initialize the elements in the first row and first column of the grid to 1
as there is only one path to reach each cell in the top-most row and left-most column.
For all columns c of the first row we assign grid [ 0 ] [ c ] = 1
For all rows r of the first column we assign grid [ r ] [ 0 ] = 1
2. All the other cells of the grid can either be reached from the cell above or from the cell to the left. Thus,
For each row r in the grid :
For each column c in the grid :
Path to current cell at [ r ] [ c ] = Path from the cell above at position [ r - 1 ] [ c ] + Path from the cell to the left at position [ r ] [ c - 1 ]
i.e grid [ r ] [ c ] = grid [ r - 1 ] [ c ] + grid [ r ] [ c - 1 ]

Time complexity : O ( m * n ), where m is the number of rows and n is the number of columns in the grid.

C++ program to find all unique paths in a grid using dynamic programming

#include<iostream>

using namespace std;

int UniquePaths (int m, int n) {

int grid[m][n];

cout << "Grid Rows : " << m << ", Columns : " << n << endl;

// All elements of 1'st column = 1
for (int r = 0; r < m ; r++)
grid[r] = 1;

// All elements of 1'st row = 1
for (int c = 0; c < n ; c++)
grid[c] = 1;

for (int r = 1; r < m ; r++) {
for (int c = 1; c < n; c++) {
grid[r][c] = grid[r-1][c] + grid[r][c-1];
}
}

return grid[m-1][n-1];
}

int main() {

int rows = 7, cols = 3, paths;
paths = UniquePaths(rows, cols);
cout << "Paths : " << paths << endl;

rows = 3, cols = 3;
paths = UniquePaths(rows, cols);
cout << "Paths : " << paths << endl;

return 0;
}

Output

Grid Rows : 7, Columns : 3
Paths : 28
Grid Rows : 3, Columns : 3
Paths : 6