ধরি একটি স্কোয়ার বোর্ড দেওয়া আছে যেইতে ক্যারেক্টার আছে। নিচের ডান কোণ থেকে (S) শুরু করে উপরের বাম কোণে (E) যেতে হবে। বাকি খানাগুলো 1-9 এর নম্বর বা X (বাধা)। এক মুভে উপ, বাম বা উপ-বাম যেতে পারা যাবে যদি বাধা না থাকে।
সর্বোচ্চ সংখ্যাগুলোর যোগফল এবং সেই যোগফল দিয়ে পাওয়া যাওয়া পাথ সংখ্যা (মডুলো 10^9+7) ফেরত দিতে হবে। পাথ না থাকলে [0,0] ফেরত দিন।
ইনপুট ["E12","1X1","21S"] হলে আউটপুট [1,2]।
সমাধানের ধাপসমূহ
n := সারি, m := কলাম
n x m x 2 আকারের 3D dp অ্যারে সংজ্ঞায়িত করুন
dp[n-1][m-1][0] = 0, dp[n-1][m-1][1] = 1
শেষ সারি এবং শেষ কলামের জন্য DP ফিল করুন
বাকি সেলগুলোর জন্য তিনটি ডিরেকশন থেকে সর্বোচ্চ ভ্যালু এবং পাথ কাউন্ট বের করুন
dp[0][0] ফেরত দিন
বेहतर বোঝার জন্য নিচের কোডটি দেখুন –
উদাহরণ
#include <bits/stdc++.h> using namespace std; void print_vector(vector<auto> v){ cout << "["; for(int i = 0; i<v.size(); i++){ cout << v[i] << ", "; } cout << "]"<<endl; } typedef long long int lli; const lli m = 1e9 + 7; lli add(lli a, lli b){ return ((a % m) + (b % m) % m); } class Solution { public: vector<int> pathsWithMaxScore(vector<string>& b) { int n = b.size(); int m = b[0].size(); vector < vector < vector <int> > > dp(n, vector < vector <int> >(m, vector <int> (2))); dp[n - 1][m - 1][0] = 0; dp[n - 1][m - 1][1] = 1; for(int i = m - 2; i >= 0; i--){ if(b[n - 1][i] == 'X')break; dp[n - 1][i][0] = b[n - 1][i] - '0' + dp[n - 1][i + 1] [0]; dp[n - 1][i][1] += dp[n - 1][i + 1][1]; } for(int i = n - 2; i >= 0; i--){ if(b[i][m - 1] == 'X')break; dp[i][m - 1][0] = b[i][m - 1] - '0' + dp[i + 1][m - 1] [0]; dp[i][m - 1][1] += dp[i + 1][m - 1][1]; } for(int i = n - 2; i >= 0; i--){ for(int j = m - 2; j >= 0; j--){ if(b[i][j] == 'X')continue; dp[i][j][0] = b[i][j] == 'E' ? 0 :b[i][j] - '0'; int maxVal = max({dp[i][j + 1][0], dp[i + 1][j][0], dp[i + 1][j + 1][0]}); if(maxVal == 0 && (b[i+1][j] != 'S' && b[i][j + 1] ! = 'S' && b[i+1][j + 1] != 'S')){ dp[i][j][0] = 0; continue; } dp[i][j][0] += maxVal; if(dp[i + 1][j][0] == maxVal){ dp[i][j][1] += dp[i + 1][j][1]; } if(dp[i + 1][j + 1][0] == maxVal){ dp[i][j][1] += dp[i + 1][j + 1][1]; } if(dp[i][j + 1][0] == maxVal){ dp[i][j][1] += dp[i][j + 1][1]; } dp[i][j][1] %= m; dp[i][j][0] %= m; } } return dp[0][0]; } }; main(){ Solution ob; vector<string> v = {"E12","1X1","21S"}; print_vector(ob.pathsWithMaxScore(v)); }ইনপুট
{"E12","1X1","21S"}আউটপুট
[1, 2, ]
