# Leetcode 063 不同路徑|| Python C 詳細題解

```輸入:
[
[0,0,0],
[0,1,0],
[0,0,0]
]

3x3 網格的正中間有一個障礙物。

1. 向右 -> 向右 -> 向下 -> 向下
2. 向下 -> 向下 -> 向右 -> 向右```

Python：

``````class Solution:
def uniquePathsWithObstacles(self, obstacleGrid):
"""
:type obstacleGrid: List[List[int]]
:rtype: int
"""
m = len(obstacleGrid)
if m == 0:
return 0
n = len(obstacleGrid[0])
dp = [[0 for _ in range(n)] for _ in range(m)]
#先把橫行和豎行填好
for i in range(m):
if obstacleGrid[i][0] != 1:
dp[i][0] = 1
else:#遇到障礙物就跳出，因為後面的都是0
break
for i in range(n):
if obstacleGrid[0][i] != 1:
dp[0][i] = 1
else:
break
#開始填最大的部分
for i in range(1, m):
for j in range(1, n):
#不是障礙物才填
#是障礙物的話預設以及為0了
if obstacleGrid[i][j] != 1:
dp[i][j] = dp[i-1][j] dp[i][j-1]
#返回最後一個值
return dp[m-1][n-1]``````

``````
class Solution {
public:
int uniquePathsWithObstacles(vector<vector<int>>& obstacleGrid) {
if (obstacleGrid.empty() || obstacleGrid[0].empty() || obstacleGrid[0][0] == 1) return 0;
vector<vector<int> > dp(obstacleGrid.size(), vector<int>(obstacleGrid[0].size(), 0));
for (int i = 0; i < obstacleGrid.size();   i) {
for (int j = 0; j < obstacleGrid[i].size();   j) {
//遇到障礙物設為0
if (obstacleGrid[i][j] == 1) dp[i][j] = 0;
//一開始的點設為1
else if (i == 0 && j == 0) dp[i][j] = 1;
//等於上一項，其實也就是等於1或者0，與pythoN程式碼效果相同
else if (i == 0 && j > 0) dp[i][j] = dp[i][j - 1];
else if (i > 0 && j == 0) dp[i][j] = dp[i - 1][j];
//動態轉移方程
else dp[i][j] = dp[i - 1][j]   dp[i][j - 1];
}
}
return dp.back().back();
}
};
``````