C++ . में अद्वितीय पथ II

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

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

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

1. दाएं → दाएं → नीचे → नीचे
2. नीचे → नीचे → दाएं → दाएं

आइए चरणों को देखें -

• a :=पंक्तियों की संख्या, b :=स्तंभों की संख्या
• अगर ग्रिड[a - 1,b - 1] शून्य नहीं है, तो 0 लौटाएं
• एक तालिका बनाएं जिसका क्रम a x b है, और नाम DP है
• i के लिए :=b – 1 से 0 तक
  • अगर ग्रिड[a – 1, i], तो तोड़ दें, अन्यथा DP[a – 1, i] :=1
• i के लिए:=a – 1 से 0 तक
  • अगर ग्रिड[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] जब ग्रिड[i, j] 0 हो, अन्यथा 0
• रिटर्न डीपी[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];
   }
};
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]]

आउटपुट

2