Caminos únicos en una cuadrícula con obstáculos

Posted on by Rudeus Greyrat

Dada una cuadrícula de tamaño m * n, supongamos que comienza en (1, 1) y su objetivo es llegar a (m, n). En cualquier caso, si está en (x, y), puede ir a (x, y + 1) o (x + 1, y).
Ahora considere si se agregan algunos obstáculos a las cuadrículas. ¿Cuántos caminos únicos habría?
Un obstáculo y un espacio vacío se marcan como 1 y 0 respectivamente en la cuadrícula.

Ejemplos:  

Input: [[0, 0, 0],
        [0, 1, 0],
        [0, 0, 0]]
Output : 2
There is only one obstacle in the middle.

Método 1: recursividad

Hemos discutido un problema para contar el número de rutas únicas en una cuadrícula cuando no había ningún obstáculo presente en la cuadrícula. Pero aquí la situación es bastante diferente. Mientras nos movemos por la cuadrícula, podemos encontrar algunos obstáculos que no podemos saltar y esa forma de llegar a la esquina inferior derecha está bloqueada. 

C++

// 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){
    // 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 ;
    }
 
    return  UniquePathHelper(i+1, j, r, c, A) +
            UniquePathHelper(i, j+1, r, c, A) ;
}
 
 
int uniquePathsWithObstacles(vector<vector<int>>& A)
{
     
    int r = A.size(), c = A[0].size();
 
     
    return UniquePathHelper(0, 0, r, c, A) ;
}
 
// Driver code
int main()
{
   vector<vector<int>> A = { { 0, 0, 0 },
                             { 0, 1, 0 },
                             { 0, 0, 0 } };
                              
   cout << uniquePathsWithObstacles(A) << " \n";                                               
}

Java

// Java code to find number of unique paths
// in a Matrix
import java.io.*;
 
class GFG {
 
  static int UniquePathHelper(int i, int j, int r, int c,
                              int[][] A)
  {
    // 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;
    }
 
    return UniquePathHelper(i + 1, j, r, c, A)
      + UniquePathHelper(i, j + 1, r, c, A);
  }
 
  static int uniquePathsWithObstacles(int[][] A)
  {
 
    int r = A.length, c = A[0].length;
 
    return UniquePathHelper(0, 0, r, c, A);
  }
 
  // 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 nipun_aggarwal

Python3

# Python code to find number of unique paths
# in a Matrix
def  UniquePathHelper(i, j, r, c, A):
   
    # 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
 
    return  UniquePathHelper(i+1, j, r, c, A) + UniquePathHelper(i, j+1, r, c, A)
 
def uniquePathsWithObstacles(A):
    r,c = len(A),len(A[0])
     
    return UniquePathHelper(0, 0, r, c, A)
 
# Driver code
A = [ [ 0, 0, 0 ],
      [ 0, 1, 0 ],
      [ 0, 0, 0 ] ]
                              
print(uniquePathsWithObstacles(A))                                          
 
# This code is contributed by shinjanpatra

C#

// 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);
    return UniquePathHelper(0, 0, r, c, A);
  }
 
  static int UniquePathHelper(int i, int j, int r, int c,
                              int[, ] A)
  {
    // 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;
    }
 
    return UniquePathHelper(i + 1, j, r, c, A)
      + UniquePathHelper(i, j + 1, r, c, A);
  }
}
 
// This code is contributed by Tapesh(tapeshdua420)

Javascript

<script>
 
// JavaScript code to find number of unique paths
// in a Matrix
function  UniquePathHelper(i, j, r, c, A){
   
    // 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
 
    return  UniquePathHelper(i+1, j, r, c, A) + UniquePathHelper(i, j+1, r, c, A)
}
 
function uniquePathsWithObstacles(A){
    let r = A.length, c = A[0].length
     
    return UniquePathHelper(0, 0, r, c, A)
}
 
// Driver code
let A = [ [ 0, 0, 0 ],
      [ 0, 1, 0 ],
      [ 0, 0, 0 ] ]
                              
document.write(uniquePathsWithObstacles(A))                                          
 
// This code is contributed by shinjanpatra
 
</script>
Producción

2

Complejidad de tiempo: O (2 m * n )

Espacio Auxiliar: O(m*n)
 

Método 2: Usando DP

1) de arriba hacia abajo

La solución más eficiente a este problema se puede lograr usando programación dinámica. Como todo concepto de problema dinámico, no volveremos a calcular los subproblemas. Se construirá una array 2D temporal y el valor se almacenará utilizando el enfoque de arriba hacia abajo. 

C++

// 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 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

// 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];
 
    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 UniquePathHelper(i + 1, j, r, c, A,
                              paths)
        + UniquePathHelper(i, j + 1, r, c, A,
                           paths);
    }
  }
}
 
// This code is contributed by Tapesh(tapeshdua420)

Python3

# 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]
 
    return UniquePathHelper(i + 1, j, r, c, A, paths) + UniquePathHelper(i, j + 1, r, c, A, paths)
 
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#

// 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 UniquePathHelper(i + 1, j, r, c, A, paths)
      + UniquePathHelper(i, j + 1, r, c, A, paths);
  }
}
 
// This code is contributed by Tapesh(tapeshdua420)

Javascript

<script>
 
// 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 (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 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 ] ]
document.write(uniquePathsWithObstacles(A))
 
// This code is contributed by shinjanpatra
 
</script>
Producción

2

Complejidad del tiempo: O(m*n) 

Espacio Auxiliar: O(m*n)

2) De abajo hacia arriba

 Se construirá una array 2D temporal y el valor se almacenará utilizando el enfoque ascendente. 

Acercarse

  • Cree una array 2D del mismo tamaño que la array dada para almacenar los resultados.
  • Recorra la array creada en forma de fila y comience a completar los valores en ella.
  • Si se encuentra un obstáculo, establezca el valor en 0.
  • Para la primera fila y columna, establezca el valor en 1 si no se encuentra un obstáculo.
  • Establezca la suma de los valores derecho y superior si no hay un obstáculo presente en esa posición correspondiente en la array dada
  • Devuelve el último valor de la array 2d creada

C++

// 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];
}
 
// 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

// 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];
    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];
  }
 
  // 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

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

// 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

<script>
    // 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];
    }
       
    let A = [ [ 0, 0, 0 ],
             [ 0, 1, 0 ],
             [ 0, 0, 0 ] ];
  
    document.write(uniquePathsWithObstacles(A));
     
    // This code is contributed by suresh07.
</script>
Producción

2

Este artículo es una contribución de Rishabh Bansal . Si te gusta GeeksforGeeks y te gustaría contribuir, también puedes escribir un artículo usando write.geeksforgeeks.org o enviar tu artículo por correo a review-team@geeksforgeeks.org. Vea su artículo que aparece en la página principal de GeeksforGeeks y ayude a otros Geeks.
Escriba comentarios si encuentra algo incorrecto o si desea compartir más información sobre el tema tratado anteriormente.

Método 3: Optimización del espacio de la solución DP.

En este método, usaremos la array 2D ‘A’ dada para almacenar la respuesta anterior usando el enfoque de abajo hacia arriba.

Acercarse

  • Comience a atravesar la array 2D ‘A’ dada en forma de fila y complete los valores en ella.
  • Para la primera fila y la primera columna, establezca el valor en 1 si no se encuentra un obstáculo.
  • Para la primera fila y la primera columna, si se encuentra un obstáculo, comience a llenar 0 hasta el último índice en esa fila o columna en particular.
  • Ahora comience a recorrer desde la segunda fila y columna (p. ej.: A[ 1 ][ 1 ]).
  • Si se encuentra un obstáculo, establezca 0 en una Cuadrícula particular (p. ej.: A[i][j]); de lo contrario, establezca la suma de los valores superior e izquierdo en A[i][j].
  • Devuelve el último valor de la array 2D.

A continuación se muestra la implementación del enfoque anterior. 

C++

// CPP program for the above approach
 
#include <bits/stdc++.h>
using namespace std;
 
int uniquePathsWithObstacles(vector<vector<int> >& A)
{
 
    int r = A.size();
    int c = A[0].size();
 
    // If obstacle is at starting position
    if (A[0][0])
        return 0;
 
    //  Initializing starting position
    A[0][0] = 1;
 
    // first row all are '1' until obstacle
    for (int j = 1; j < c; j++) {
 
        if (A[0][j] == 0) {
            A[0][j] = A[0][j - 1];
        }
        else {
            // No ways to reach at this index
            A[0][j] = 0;
        }
    }
 
    // first column all are '1' until obstacle
    for (int i = 1; i < r; i++) {
 
        if (A[i][0] == 0) {
            A[i][0] = A[i - 1][0];
        }
        else {
            // No ways to reach at this index
            A[i][0] = 0;
        }
    }
 
    for (int i = 1; i < r; i++) {
 
        for (int j = 1; j < c; j++) {
            // If current cell has no obstacle
            if (A[i][j] == 0) {
 
                A[i][j] = A[i - 1][j] + A[i][j - 1];
            }
            else {
                // No ways to reach at this index
                A[i][j] = 0;
            }
        }
    }
 
    // returning the bottom right
    // corner of Grid
    return A[r - 1];
}
 
// Driver Code
 
int main()
{
 
    vector<vector<int> > A
        = { { 0, 0, 0 }, { 0, 1, 0 }, { 0, 0, 0 } };
 
    cout << uniquePathsWithObstacles(A) << "\n";
 
    return 0;
}
// This code is contributed by hemantraj712

Java

// Java program for the above approach
class GFG {
 
    static int uniquePathsWithObstacles(int[][] A)
    {
 
        int r = A.length;
        int c = A[0].length;
 
        // If obstacle is at starting position
        if (A[0][0] != 0)
            return 0;
 
        //  Initializing starting position
        A[0][0] = 1;
 
        // first row all are '1' until obstacle
        for (int j = 1; j < c; j++) {
 
            if (A[0][j] == 0) {
                A[0][j] = A[0][j - 1];
            }
            else {
                // No ways to reach at this index
                A[0][j] = 0;
            }
        }
 
        // first column all are '1' until obstacle
        for (int i = 1; i < r; i++) {
 
            if (A[i][0] == 0) {
                A[i][0] = A[i - 1][0];
            }
            else {
                // No ways to reach at this index
                A[i][0] = 0;
            }
        }
 
        for (int i = 1; i < r; i++)
        {
 
            for (int j = 1; j < c; j++)
            {
               
                // If current cell has no obstacle
                if (A[i][j] == 0) {
 
                    A[i][j] = A[i - 1][j] + A[i][j - 1];
                }
                else {
                    // No ways to reach at this index
                    A[i][j] = 0;
                }
            }
        }
 
        // returning the bottom right
        // corner of Grid
        return A[r - 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 rajsanghavi9.

Python3

# Python program for the above approach
 
 
def uniquePathsWithObstacles(A):
 
    r = len(A)
    c = len(A[0])
 
    # If obstacle is at starting position
    if (A[0][0]):
        return 0
 
    #  Initializing starting position
    A[0][0] = 1
 
    # first row all are '1' until obstacle
    for j in range(1,c):
 
        if (A[0][j] == 0):
            A[0][j] = A[0][j - 1]
        else:
            # No ways to reach at this index
            A[0][j] = 0
 
    # first column all are '1' until obstacle
    for i in range(1,r):
 
        if (A[i][0] == 0):
            A[i][0] = A[i - 1][0]
        else:
            # No ways to reach at this index
            A[i][0] = 0
 
    for i in range(1,r):
 
        for j in range(1,c):
            # If current cell has no obstacle
            if (A[i][j] == 0):
 
                A[i][j] = A[i - 1][j] + A[i][j - 1]
            else:
                # No ways to reach at this index
                A[i][j] = 0
 
    # returning the bottom right
    # corner of Grid
    return A[r - 1]
 
# Driver Code
 
A = [ [ 0, 0, 0 ], [ 0, 1, 0 ], [ 0, 0, 0 ] ]
 
print(uniquePathsWithObstacles(A))
 
# This code is contributed by shinjanpatra

C#

// C# program for the above approach
using System;
using System.Collections.Generic;
 
class Program {
  static int uniquePathsWithObstacles(int[, ] A)
  {
    int r = A.GetLength(0);
    int c = A.GetLength(1);
 
    // If obstacle is at starting position
    if (A[0, 0] != 0)
      return 0;
 
    //  Initializing starting position
    A[0, 0] = 1;
    for (int j = 1; j < c; j++) {
      if (A[0, j] == 0) {
        A[0, j] = A[0, j - 1];
      }
      else {
        A[0, j] = 0;
      }
    }
 
    // first row all are '1' until obstacle
    for (int i = 1; i < r; i++) {
      if (A[i, 0] == 0) {
        A[i, 0] = A[i - 1, 0];
      }
      else {
        // No ways to reach at this index
        A[i, 0] = 0;
      }
    }
 
    for (int i = 1; i < r; i++) {
      for (int j = 1; j < c; j++) {
        // If current cell has no obstacle
        if (A[i, j] == 0) {
          A[i, j] = A[i - 1, j] + A[i, j - 1];
        }
        else {
          // No ways to reach at this index
          A[i, j] = 0;
        }
      }
    }
    // returning the bottom right
    // corner of Grid
    return A[r - 1, c - 1];
  }
   
  // Driver code
  public static void Main(String[] args)
  {
 
    int[, ] A = new int[3, 3] { { 0, 0, 0 },
                               { 0, 1, 0 },
                               { 0, 0, 0 } };
 
    Console.WriteLine(uniquePathsWithObstacles(A));
  }
}
 
// This code is contributed by Tapesh (tapeshdua420)

Javascript

<script>
 
// JavaScript program for the above approach
function uniquePathsWithObstacles(A){
 
    let r = A.length
    let c = A[0].length
 
    // If obstacle is at starting position
    if (A[0][0])
        return 0
 
    //  Initializing starting position
    A[0][0] = 1
 
    // first row all are '1' until obstacle
    for(let j = 1; j < c; j++)
    {
        if (A[0][j] == 0)
            A[0][j] = A[0][j - 1]
        else
            // No ways to reach at this index
            A[0][j] = 0
    }
 
    // first column all are '1' until obstacle
    for(let i = 1; i < r; i++){
 
        if (A[i][0] == 0)
            A[i][0] = A[i - 1][0]
        else
            // No ways to reach at this index
            A[i][0] = 0
    }
 
   for(let i = 1; i < r; i++){
 
      for(let j = 1; j < c; j++){
            // If current cell has no obstacle
            if (A[i][j] == 0)
 
                A[i][j] = A[i - 1][j] + A[i][j - 1]
            else
                // No ways to reach at this index
                A[i][j] = 0
      }
   }
 
    // returning the bottom right
    // corner of Grid
    return A[r - 1]
}
 
// Driver Code
let A = [ [ 0, 0, 0 ], [ 0, 1, 0 ], [ 0, 0, 0 ] ]
document.write(uniquePathsWithObstacles(A),"</br>")
 
// This code is contributed by shinjanpatra
 
</script>
Producción

2

Tiempo Complejidad: O(m*n)  
Espacio Auxiliar: O(1)

Publicación traducida automáticamente

Artículo escrito por GeeksforGeeks-1 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA

Deja una respuesta

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *