Đường dẫn duy nhất II trong C ++

Giả sử có một rô bốt được đặt ở góc trên bên trái của lưới n x m (n hàng và m cột). Robot chỉ có thể di chuyển bên dưới hoặc bên phải tại bất kỳ thời điểm nào. Robot muốn tiếp cận góc dưới cùng bên phải của lưới (được đánh dấu 'KẾT THÚC trong sơ đồ bên dưới).

Một số ô trong lưới được đánh dấu, đó sẽ được coi là chướng ngại vật. Vậy chúng ta phải tìm xem có bao nhiêu con đường độc đạo khả dĩ? Ví dụ:nếu lưới có dạng [[0,0,0], [0,1,0], [0,0,0]], thì lưới sẽ giống như bên dưới -

Robo
	Ám ảnh
		HẾT

Đầu ra sẽ là 2, Vì vậy, có tổng cộng 2 cách khác nhau để đạt được từ vị trí bắt đầu đến vị trí kết thúc. Những con đường này -

Phải → Phải → Xuống → Xuống
Xuống → Xuống → Phải → Phải

Hãy để chúng tôi xem các bước -

a:=số hàng, b:=số cột
nếu lưới [a - 1, b - 1] khác 0, thì trả về 0
tạo một bảng có thứ tự là a x b và tên là DP
for i:=b - 1 xuống 0
- nếu lưới [a - 1, i] thì ngắt, ngược lại DP [a - 1, i]:=1
for i:=a - 1 xuống 0
- nếu lưới [i, b - 1] thì ngắt, ngược lại DP [i, b - 1]:=1
for i:=a - 2 xuống 0
- cho j:=b - 2 xuống 0
  - DP [i, j]:=DP [i + 1, j] + DP [i, j + 1] khi lưới [i, j] là 0, nếu không thì 0
trả lại DP [0, 0]

Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơn -

Ví dụ

#include <bits/stdc++.h>
using namespace std;
typedef long long int lli;
class Solution {
   public:
   int uniquePathsWithObstacles(vector<vector<int>>& obstacleGrid) {
      int a = obstacleGrid.size();
      int b = obstacleGrid[0].size();
         if(!a || !b) return 0;
      if(obstacleGrid[a - 1][b - 1])return 0;
      vector < vector <lli> > dp(a, vector <lli>(b));
      for(int i = b - 1; i >= 0; i--)if(obstacleGrid[a-1][i]) break; else dp[a-1][i] = 1;
      for(int i = a - 1; i >= 0; i--)if(obstacleGrid[i][b - 1]) break; else dp[i][b-1] = 1 ;
      for(int i = a-2; i >= 0; i--){
         for(int j = b-2 ; j >= 0; j--)dp[i][j] = !obstacleGrid[i][j]? dp[i+1][j] + dp[i][j+1] : 0;
      }
      return dp[0][0];
   }
};
main(){
   Solution ob;
   vector<vector<int>> v = {{0,0,0},{0,1,0},{0,0,0}};
   cout << ob.uniquePathsWithObstacles(v);
}

Đầu vào

[[0,0,0],[0,1,0],[0,0,0]]