C++ में अद्वितीय पथ II (Unique Paths II)

मान लीजिए एक रोबोट n x m ग्रिड (n पंक्तियां और m कॉलम) के शीर्ष-बाएं कोने पर स्थित है। रोबोट किसी भी समय केवल नीचे या दाएं जा सकता है। रोबोट ग्रिड के नीचे-दाएं कोने (आरेख में 'END' से चिह्नित) तक पहुंचना चाहता है।

ग्रिड में कुछ सेल चिह्नित हैं, जिन्हें बाधाएं (obstacles) माना जाएगा। तो हमें ढूंढना है कि कितने संभावित अद्वितीय पथ हैं? उदाहरण के लिए यदि ग्रिड [[0,0,0],[0,1,0],[0,0,0]] है, तो ग्रिड इस तरह होगा:

रोबो
	बाधा
		END

आउटपुट 2 होगा, यानी प्रारंभिक स्थिति से अंतिम स्थिति तक पहुंचने के कुल 2 अलग-अलग तरीके हैं। ये पथ हैं:

दाएं → दाएं → नीचे → नीचे
नीचे → नीचे → दाएं → दाएं

आइए चरण देखें:

a := पंक्तियों की संख्या, b := कॉलम की संख्या
यदि grid[a – 1, b - 1] शून्येतर है, तो 0 वापस करें
a x b क्रम की एक तालिका बनाएं, नाम DP
i := b – 1 से 0 तक:
- यदि grid[a – 1, i], तो ब्रेक, अन्यथा DP[a – 1, i] := 1
i := a – 1 से 0 तक:
- यदि grid[i, b - 1], तो ब्रेक, अन्यथा DP[i, b – 1] := 1
i := a – 2 से 0 तक:
- j := b – 2 से 0 तक:
  - DP[i, j] := DP[i + 1, j] + DP[i, j + 1] जब grid[i, j] 0 हो, अन्यथा 0
DP[0, 0] वापस करें

उदाहरण

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

int main(){
    Solution ob;
    vector<vector<int>> v = {{0,0,0},{0,1,0},{0,0,0}};
    cout << ob.uniquePathsWithObstacles(v);
}

इनपुट

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