智能算法设计：具有障碍物的网格中的唯一路径

本文概述

• C ++
• python

给定一个大小为m * n的网格, 让我们假设你从(1, 1)开始, 而你的目标是达到(m, n)。无论如何, 如果你在(x, y)上, 则可以转到(x, y + 1)或(x + 1, y)。

现在考虑是否在网格中添加了一些障碍。会有多少条独特的路径？

障碍物和空白区域在网格中分别标记为1和0。

例子：

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

讨论了在无障碍物的情况下计算网格中唯一路径的问题。但这里的情况完全不同。。在网格中移动时, 我们会遇到一些无法跳跃的障碍, 因此无法到达右下角。

使用动态编程可以解决该问题的最有效方法。像每个动态问题概念一样, 我们不会重新计算子问题。将构造一个临时2D矩阵, 并使用自下而上的方法存储值。

方法

• 创建与给定矩阵大小相同的2D矩阵以存储结果。
• 遍历创建的数组行并开始填充其中的值。
• 如果发现障碍物, 则将该值设置为0。
• 对于第一行和第一列, 如果未发现障碍物, 则将该值设置为1。
• 如果给定母体上的相应位置不存在障碍物, 则设置右值和上限值的和
• 返回创建的二维矩阵的最后一个值

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

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

输出如下

2