একটি n x m গ্রিডে রোবট টপ-লেফট থেকে বটম-রাইট যেতে চায়। শুধু ডাউন বা রাইট মুভ করতে পারে। কিছু সেলে বাধা (obstacle) আছে। কতটুকু ইউনিক পাথ আছে তা বের করতে হবে।
উদাহরণ: grid = [[0,0,0],[0,1,0],[0,0,0]] আউটপুট: ২ (দুটি পাথ: Right→Right→Down→Down এবং Down→Down→Right→Right)।
সমাধান: DP টেবিল ব্যবহার। বটম-রাইট থেকে টপ-লেফট দিকে DP ভ্যালু ক্যালকুলেট। বাধা থাকলে DP=০, অন্যথায় নিচ ও ডানের DP যোগফল।
উদাহরণ
#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
