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

2021年4月1日16:42:39 发表评论 557 次浏览

## 本文概述

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

### 方法

• 创建与给定矩阵大小相同的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``