Assume we are starting at (1, 1) and want to reach (m, n), given a grid[][] of size m * n. At any moment, should we be on (x, y, we can either proceed to (x, y + 1) or (x + 1, y). The goal is to determine the count of distinct paths should certain grid obstacles be introduced.
The grid marks space and an obstruction as 1 and 0 correspondingly.
Input:
grid[][] = [[0, 0, 0],
[0, 1, 0],
[0, 0, 0]]
Output: 2
Explanation: There are two ways to reach the bottom-right corner:
Right -> Right -> Down -> Down
Down -> Down -> Right -> Right
Input:
grid[][] = [[0, 1],
[0, 0]]
Output: 1
Explanation: There is only one way to reach the bottom-right corner:
Down -> Right Table of Content
- Using Recursion – O(2^(m*n)) Time and O(m+n) Space
- Using Top-Down DP(Memoization) – O(m*n) Time and O(m*n) Space
- Using Bottom-Up DP (Tabulation) – O(m*n) Time and O(m*n) Space
- Using Space Optimised DP – O(m*n) Time and O(n) Space
Using Recursion – O(2^(m*n)) Time and O(m+n) Space
We have covered the issue of counting the distinct paths in a Grid when the grid lacked any obstruction. But here the circumstances are somewhat different. We can come across some barriers in the grid that we cannot leap beyond, hence the path to the bottom right corner is blocked.
This method will investigate two primary examples from every cell in both directions:
- Go to the cell under your present position.
- Advance to the cell to the right of your present location.
Base Cases:
If i == r or j == c: The current position is out of bounds, so there are no paths available. Return 0.
If grid[i][j] == 1: The current cell is an obstacle, so it cannot be used. Return 0.
If i == r-1 and j == c-1: The function has reached the destination, so there is exactly one path. Return 1.
The recurrence relation will be:
UniquePathHelper(i, j, r, c, grid) = UniquePathHelper(i+1, j, r, c, grid) + UniquePathHelper(i, j+1, r, c, grid)C++
// C++ code to find number of unique paths
// using Recursion
#include <bits/stdc++.h>
using namespace std;
// Helper function to find unique paths recursively
int UniquePathHelper(int i, int j, int r, int c,
vector<vector<int>>& grid) {
// If out of bounds, return 0
if(i == r || j == c) {
return 0;
}
// If cell is an obstacle, return 0
if(grid[i][j] == 1) {
return 0;
}
// If reached the bottom-right cell, return 1
if(i == r-1 && j == c-1) {
return 1;
}
// Recur for the cell below and the cell to the right
return UniquePathHelper(i+1, j, r, c, grid) +
UniquePathHelper(i, j+1, r, c, grid);
}
// Function to find unique paths with obstacles
int uniquePathsWithObstacles(vector<vector<int>>& grid) {
int r = grid.size(), c = grid[0].size();
return UniquePathHelper(0, 0, r, c, grid);
}
int main() {
// Hardcoded grid with obstacles
vector<vector<int>> grid = { { 0, 0, 0 },
{ 0, 1, 0 },
{ 0, 0, 0 } };
cout << uniquePathsWithObstacles(grid);
}Java
// Java code to find number of unique paths
// using Recursion
import java.util.*;
class GfG {
// Helper function to find unique paths recursively
static int UniquePathHelper(int i, int j, int r, int c,
int[][] grid) {
// If out of bounds, return 0
if(i == r || j == c) {
return 0;
}
// If cell is an obstacle, return 0
if(grid[i][j] == 1) {
return 0;
}
// If reached the bottom-right cell, return 1
if(i == r-1 && j == c-1) {
return 1;
}
// Recur for the cell below and the cell to the right
return UniquePathHelper(i+1, j, r, c, grid) +
UniquePathHelper(i, j+1, r, c, grid);
}
// Function to find unique paths with obstacles
static int uniquePathsWithObstacles(int[][] grid) {
int r = grid.length, c = grid[0].length;
return UniquePathHelper(0, 0, r, c, grid);
}
public static void main(String[] args) {
int[][] grid = { { 0, 0, 0 },
{ 0, 1, 0 },
{ 0, 0, 0 } };
System.out.println(uniquePathsWithObstacles(grid));
}
}Python
# Python code to find number of unique paths
# using Recursion
# Helper function to find unique paths recursively
def UniquePathHelper(i, j, r, c, grid):
# If out of bounds, return 0
if i == r or j == c:
return 0
# If cell is an obstacle, return 0
if grid[i][j] == 1:
return 0
# If reached the bottom-right cell, return 1
if i == r-1 and j == c-1:
return 1
# Recur for the cell below and the cell to the right
return UniquePathHelper(i+1, j, r, c, grid) + \
UniquePathHelper(i, j+1, r, c, grid)
# Function to find unique paths with obstacles
def uniquePathsWithObstacles(grid):
r, c = len(grid), len(grid[0])
return UniquePathHelper(0, 0, r, c, grid)
if __name__ == "__main__":
grid = [[0, 0, 0],
[0, 1, 0],
[0, 0, 0]]
print(uniquePathsWithObstacles(grid))C#
// C# code to find number of unique paths
// using Recursion
using System;
using System.Collections.Generic;
class GfG {
// Helper function to find unique paths recursively
static int UniquePathHelper(int i, int j, int r, int c,
int[,] grid) {
// If out of bounds, return 0
if(i == r || j == c) {
return 0;
}
// If cell is an obstacle, return 0
if(grid[i, j] == 1) {
return 0;
}
// If reached the bottom-right cell, return 1
if(i == r-1 && j == c-1) {
return 1;
}
// Recur for the cell below and the cell to the right
return UniquePathHelper(i+1, j, r, c, grid) +
UniquePathHelper(i, j+1, r, c, grid);
}
// Function to find unique paths with obstacles
static int uniquePathsWithObstacles(int[,] grid) {
int r = grid.GetLength(0), c = grid.GetLength(1);
return UniquePathHelper(0, 0, r, c, grid);
}
static void Main() {
int[,] grid = { { 0, 0, 0 },
{ 0, 1, 0 },
{ 0, 0, 0 } };
Console.WriteLine(uniquePathsWithObstacles(grid));
}
}JavaScript
// Javascript code to find number of unique paths
// using Recursion
// Helper function to find unique paths recursively
function UniquePathHelper(i, j, r, c, grid) {
// If out of bounds, return 0
if (i === r || j === c) {
return 0;
}
// If cell is an obstacle, return 0
if (grid[i][j] === 1) {
return 0;
}
// If reached the bottom-right cell, return 1
if (i === r - 1 && j === c - 1) {
return 1;
}
// Recur for the cell below and the cell to the right
return UniquePathHelper(i + 1, j, r, c, grid)
+ UniquePathHelper(i, j + 1, r, c, grid);
}
// Function to find unique paths with obstacles
function uniquePathsWithObstacles(grid)
{
let r = grid.length, c = grid[0].length;
return UniquePathHelper(0, 0, r, c, grid);
}
const grid = [ [ 0, 0, 0 ], [ 0, 1, 0 ], [ 0, 0, 0 ] ];
console.log(uniquePathsWithObstacles(grid));Output
2