Unique paths in a Grid with Obstacles using Dynamic Programming
1) Top-Down
The most efficient solution to this problem can be achieved using dynamic programming. Like every dynamic problem concept, we will not recompute the subproblems. A temporary 2D matrix will be constructed and value will be stored using the top-down approach.
// C++ code to find number of unique paths
// in a Matrix
#include <bits/stdc++.h>
using namespace std;
int UniquePathHelper(int i, int j, int r, int c,
vector<vector<int> >& A,
vector<vector<int> >& paths)
{
// boundary condition or constraints
if (i == r || j == c) {
return 0;
}
if (A[i][j] == 1) {
return 0;
}
// base case
if (i == r - 1 && j == c - 1) {
return 1;
}
if (paths[i][j] != -1) {
return paths[i][j];
}
return paths[i][j]
= UniquePathHelper(i + 1, j, r, c, A, paths)
+ UniquePathHelper(i, j + 1, r, c, A, paths);
}
int uniquePathsWithObstacles(vector<vector<int> >& A)
{
int r = A.size(), c = A[0].size();
// create a 2D-matrix and initializing
// with value 0
vector<vector<int> > paths(r, vector<int>(c, -1));
return UniquePathHelper(0, 0, r, c, A, paths);
}
// Driver code
int main()
{
vector<vector<int> > A
= { { 0, 0, 0 }, { 0, 1, 0 }, { 0, 0, 0 } };
cout << uniquePathsWithObstacles(A) << " \n";
}
// Java code to find number of unique paths
// in a Matrix
import java.util.*;
public class Main {
public static void main(String[] args)
{
int[][] A
= { { 0, 0, 0 }, { 0, 1, 0 }, { 0, 0, 0 } };
System.out.println(uniquePathsWithObstacles(A));
}
public static int uniquePathsWithObstacles(int[][] A)
{
int r = A.length;
int c = A[0].length;
// create a 2D-matrix and initializing
// with value 0
int[][] paths = new int[r][c];
for (int i = 0; i < r; i++) {
Arrays.fill(paths[i], -1);
}
return UniquePathHelper(0, 0, r, c, A, paths);
}
public static int UniquePathHelper(int i, int j, int r,
int c, int[][] A,
int[][] paths)
{
// boundary condition or constraints
if (i == r || j == c) {
return 0;
}
else if (A[i][j] == 1) {
return 0;
}
// base case
else if (i == r - 1 && j == c - 1) {
return 1;
}
else if (paths[i][j] != -1) {
return paths[i][j];
}
else {
return paths[i][j]
= UniquePathHelper(i + 1, j, r, c, A, paths)
+ UniquePathHelper(i, j + 1, r, c, A,
paths);
}
}
}
// This code is contributed by Tapesh(tapeshdua420)
# Python code to find number of unique paths
# in a Matrix
def UniquePathHelper(i, j, r, c, A, paths):
# boundary condition or constraints
if (i == r or j == c):
return 0
if (A[i][j] == 1):
return 0
# base case
if (i == r - 1 and j == c - 1):
return 1
if (paths[i][j] != -1):
return paths[i][j]
paths[i][j] = UniquePathHelper(
i + 1, j, r, c, A, paths) + UniquePathHelper(i, j + 1, r, c, A, paths)
return paths[i][j]
def uniquePathsWithObstacles(A):
r, c = len(A), len(A[0])
# create a 2D-matrix and initializing
# with value 0
paths = [[-1 for i in range(c)]for j in range(r)]
return UniquePathHelper(0, 0, r, c, A, paths)
# Driver code
A = [[0, 0, 0], [0, 1, 0], [0, 0, 0]]
print(uniquePathsWithObstacles(A))
# code is contributed by shinjanpatra
// C# code to find number of unique paths
// in a Matrix
using System;
class Program {
// Driver code
static void Main(string[] args)
{
int[, ] A = new int[3, 3] { { 0, 0, 0 },
{ 0, 1, 0 },
{ 0, 0, 0 } };
Console.WriteLine(uniquePathsWithObstacles(A));
}
static int uniquePathsWithObstacles(int[, ] A)
{
int r = A.GetLength(0);
int c = A.GetLength(1);
// create a 2D-matrix and initializing
// with value -1
int[, ] paths = new int[r, c];
for (int i = 0; i < r; i++) {
for (int j = 0; j < c; j++) {
paths[i, j] = -1;
}
}
return UniquePathHelper(0, 0, r, c, A, paths);
}
static int UniquePathHelper(int i, int j, int r, int c,
int[, ] A, int[, ] paths)
{
// boundary condition or constraints
if (i == r || j == c) {
return 0;
}
if (A[i, j] == 1) {
return 0;
}
// base case
if (i == r - 1 && j == c - 1) {
return 1;
}
if (paths[i, j] != -1) {
return paths[i, j];
}
return paths[i, j]
= UniquePathHelper(i + 1, j, r, c, A, paths)
+ UniquePathHelper(i, j + 1, r, c, A, paths);
}
}
// This code is contributed by Tapesh(tapeshdua420)
// JavaScript code to find number of unique paths
// in a Matrix
function UniquePathHelper(i, j, r, c, A, paths)
{
// boundary condition or constraints
if (i == r || j == c) {
return 0;
}
if (paths[i][j] == 1) {
return 0;
}
// base case
if (i == r - 1 && j == c - 1) {
return 1;
}
if (paths[i][j] != -1) {
return paths[i][j];
}
return paths[i][j]
= UniquePathHelper(i + 1, j, r, c, A, paths)
+ UniquePathHelper(i, j + 1, r, c, A, paths);
}
function uniquePathsWithObstacles(A)
{
let r = A.length, c = A[0].length;
// create a 2D-matrix and initializing
// with value 0
let paths = new Array(c);
for(let i = 0; i < r; i++){
paths[i] = new Array(c).fill(-1);
}
return UniquePathHelper(0, 0, r, c, A, paths);
}
// Driver code
let A = [ [ 0, 0, 0 ], [ 0, 1, 0 ], [ 0, 0, 0 ] ]
console.log(uniquePathsWithObstacles(A))
// This code is contributed by shinjanpatra
Output
2
Time Complexity: O(m*n)
Auxiliary Space: O(m*n)
2) Bottom-Up
A temporary 2D matrix will be constructed and value will be stored using the bottom-up approach.
Approach:
- Create a 2D matrix of the same size as the given matrix to store the results.
- Traverse through the created array row-wise and start filling the values in it.
- If an obstacle is found, set the value to 0.
- For the first row and column, set the value to 1 if an obstacle is not found.
- Set the sum of the right and the upper values if an obstacle is not present at that corresponding position in the given matrix
- Return the last value of the created 2d matrix
Below is the implementation of the above approach:
// C++ code to find number of unique paths
// in a Matrix
#include<bits/stdc++.h>
using namespace std;
int uniquePathsWithObstacles(vector<vector<int>>& A)
{
int r = A.size(), c = A[0].size();
// create a 2D-matrix and initializing
// with value 0
vector<vector<int>> paths(r, vector<int>(c, 0));
// Initializing the left corner if
// no obstacle there
if (A[0][0] == 0)
paths[0][0] = 1;
// Initializing first column of
// the 2D matrix
for(int i = 1; i < r; i++)
{
// If not obstacle
if (A[i][0] == 0)
paths[i][0] = paths[i-1][0];
}
// Initializing first row of the 2D matrix
for(int j = 1; j < c; j++)
{
// If not obstacle
if (A[0][j] == 0)
paths[0][j] = paths[0][j - 1];
}
for(int i = 1; i < r; i++)
{
for(int j = 1; j < c; j++)
{
// If current cell is not obstacle
if (A[i][j] == 0)
paths[i][j] = paths[i - 1][j] +
paths[i][j - 1];
}
}
// Returning the corner value
// of the matrix
return paths[r - 1][c - 1];//it is not visible in the article, instread only paths[r - 1] is visible so please change it
}
// Driver code
int main()
{
vector<vector<int>> A = { { 0, 0, 0 },
{ 0, 1, 0 },
{ 0, 0, 0 } };
cout << uniquePathsWithObstacles(A) << " \n";
}
// This code is contributed by ajaykr00kj
// Java code to find number of unique paths
// in a Matrix
public class Main
{
static int uniquePathsWithObstacles(int[][] A)
{
int r = 3, c = 3;
// create a 2D-matrix and initializing
// with value 0
int[][] paths = new int[r][c];
for(int i = 0; i < r; i++)
{
for(int j = 0; j < c; j++)
{
paths[i][j] = 0;
}
}
// Initializing the left corner if
// no obstacle there
if (A[0][0] == 0)
paths[0][0] = 1;
// Initializing first column of
// the 2D matrix
for(int i = 1; i < r; i++)
{
// If not obstacle
if (A[i][0] == 0)
paths[i][0] = paths[i - 1][0];
}
// Initializing first row of the 2D matrix
for(int j = 1; j < c; j++)
{
// If not obstacle
if (A[0][j] == 0)
paths[0][j] = paths[0][j - 1];
}
for(int i = 1; i < r; i++)
{
for(int j = 1; j < c; j++)
{
// If current cell is not obstacle
if (A[i][j] == 0)
paths[i][j] = paths[i - 1][j] +
paths[i][j - 1];
}
}
// Returning the corner value
// of the matrix
return paths[r - 1][c - 1];
}
// Driver code
public static void main(String[] args) {
int[][] A = { { 0, 0, 0 },
{ 0, 1, 0 },
{ 0, 0, 0 } };
System.out.print(uniquePathsWithObstacles(A));
}
}
// This code is contributed by divyeshrabadiya07.
# Python code to find number of unique paths in a
# matrix with obstacles.
def uniquePathsWithObstacles(A):
# create a 2D-matrix and initializing with value 0
paths = [[0]*len(A[0]) for i in A]
# initializing the left corner if no obstacle there
if A[0][0] == 0:
paths[0][0] = 1
# initializing first column of the 2D matrix
for i in range(1, len(A)):
# If not obstacle
if A[i][0] == 0:
paths[i][0] = paths[i-1][0]
# initializing first row of the 2D matrix
for j in range(1, len(A[0])):
# If not obstacle
if A[0][j] == 0:
paths[0][j] = paths[0][j-1]
for i in range(1, len(A)):
for j in range(1, len(A[0])):
# If current cell is not obstacle
if A[i][j] == 0:
paths[i][j] = paths[i-1][j] + paths[i][j-1]
# returning the corner value of the matrix
return paths[-1][-1]
# Driver Code
A = [[0, 0, 0], [0, 1, 0], [0, 0, 0]]
print(uniquePathsWithObstacles(A))
// C# code to find number of unique paths
// in a Matrix
using System;
class GFG {
static int uniquePathsWithObstacles(int[,] A)
{
int r = 3, c = 3;
// create a 2D-matrix and initializing
// with value 0
int[,] paths = new int[r,c];
for(int i = 0; i < r; i++)
{
for(int j = 0; j < c; j++)
{
paths[i, j] = 0;
}
}
// Initializing the left corner if
// no obstacle there
if (A[0, 0] == 0)
paths[0, 0] = 1;
// Initializing first column of
// the 2D matrix
for(int i = 1; i < r; i++)
{
// If not obstacle
if (A[i, 0] == 0)
paths[i, 0] = paths[i - 1, 0];
}
// Initializing first row of the 2D matrix
for(int j = 1; j < c; j++)
{
// If not obstacle
if (A[0, j] == 0)
paths[0, j] = paths[0, j - 1];
}
for(int i = 1; i < r; i++)
{
for(int j = 1; j < c; j++)
{
// If current cell is not obstacle
if (A[i, j] == 0)
paths[i, j] = paths[i - 1, j] +
paths[i, j - 1];
}
}
// Returning the corner value
// of the matrix
return paths[r - 1, c - 1];
}
// Driver code
static void Main() {
int[,] A = { { 0, 0, 0 },
{ 0, 1, 0 },
{ 0, 0, 0 } };
Console.WriteLine(uniquePathsWithObstacles(A));
}
}
// This code is contributed by divyesh072019.
// Javascript code to find number of unique paths
// in a Matrix
function uniquePathsWithObstacles(A)
{
let r = 3, c = 3;
// create a 2D-matrix and initializing
// with value 0
let paths = new Array(r);
for(let i = 0; i < r; i++)
{
paths[i] = new Array(c);
for(let j = 0; j < c; j++)
{
paths[i][j] = 0;
}
}
// Initializing the left corner if
// no obstacle there
if (A[0][0] == 0)
paths[0][0] = 1;
// Initializing first column of
// the 2D matrix
for(let i = 1; i < r; i++)
{
// If not obstacle
if (A[i][0] == 0)
paths[i][0] = paths[i - 1][0];
}
// Initializing first row of the 2D matrix
for(let j = 1; j < c; j++)
{
// If not obstacle
if (A[0][j] == 0)
paths[0][j] = paths[0][j - 1];
}
for(let i = 1; i < r; i++)
{
for(let j = 1; j < c; j++)
{
// If current cell is not obstacle
if (A[i][j] == 0)
paths[i][j] = paths[i - 1][j] +
paths[i][j - 1];
}
}
// Returning the corner value
// of the matrix
return paths[r - 1][c -1];
}
let A = [ [ 0, 0, 0 ],
[ 0, 1, 0 ],
[ 0, 0, 0 ] ];
console.log(uniquePathsWithObstacles(A));
// This code is contributed by suresh07.
Output
2
Time Complexity: O(m*n)
Auxiliary Space: O(m*n)
Unique paths in a Grid with Obstacles
Given a grid of size m * n, let us assume you are starting at (1, 1) and your goal is to reach (m, n). At any instance, if you are on (x, y), you can either go to (x, y + 1) or (x + 1, y).
Now consider if some obstacles are added to the grids. How many unique paths would there be?
An obstacle and space are marked as 1 and 0 respectively in the grid.
Examples:
Input: [[0, 0, 0],
[0, 1, 0],
[0, 0, 0]]Output: 2
There is only one obstacle in the middle.