C++ এ অনন্য পাথ II

ধরুন একটি রোবট একটি n x m গ্রিডের (n সারি এবং m কলাম) উপরের-বাম কোণে অবস্থিত। রোবটটি যেকোনো সময় যে কোনো সময় নিচের দিকে বা ডান দিকে যেতে পারে। রোবটটি গ্রিডের নীচে-ডান কোণায় পৌঁছাতে চায় (নীচের চিত্রে 'END চিহ্নিত)।

গ্রিডের কিছু সেল চিহ্নিত করা হয়েছে, যেগুলোকে বাধা হিসেবে গণ্য করা হবে। তাহলে আমাদের খুঁজে বের করতে হবে কতগুলো সম্ভাব্য অনন্য পথ? উদাহরণস্বরূপ যদি গ্রিডটি [[0,0,0],[0,1,0],[0,0,0]] এর মতো হয়, তাহলে গ্রিডটি নীচের মত হবে −

Robo
	Obs
		শেষ

আউটপুট হবে 2, তাই স্টার্ট পজিশন থেকে শেষ পজিশনে পৌঁছানোর মোট 2টি ভিন্ন উপায় রয়েছে। এই পথগুলি হল −

ডান → ডান → নিচে → নিচে
নিচে → নিচে → ডান → ডান

আসুন ধাপগুলো দেখি -

a :=সারির সংখ্যা, b :=কলামের সংখ্যা
যদি গ্রিড[a – 1,b - 1] শূন্য না হয়, তাহলে 0 ফেরত দিন
একটি টেবিল তৈরি করুন যার ক্রম একটি 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]]