ধরুন আমাদের একটি N x N গ্রিড আছে, এটি চেরি দিয়ে ভরা। প্রতিটি কক্ষে নিম্নরূপ সম্ভাব্য পূর্ণসংখ্যাগুলির মধ্যে একটি রয়েছে -
- 0 − নির্দেশ করে ঘর খালি, তাই আমরা পার হতে পারি
- 1 - ইঙ্গিত করে কোষে একটি চেরি রয়েছে, যা আমরা তুলতে পারি এবং এর মধ্য দিয়ে যেতে পারি
- -1 − ইঙ্গিত করে যে কোষে একটি কাঁটা রয়েছে যা পথকে বাধা দেয়
এই কয়েকটি নিয়ম-
ব্যবহার করে আমাদের সর্বোচ্চ সংখ্যক চেরি সংগ্রহ করতে হবে- পজিশন থেকে শুরু করুন (0, 0) এবং (N-1, N-1) এ শেষ করুন বৈধ পাথ সেলের মাধ্যমে ডানে বা নিচে সরে গিয়ে
- কোষে পৌঁছানোর পর (N-1, N-1), বৈধ পথ কোষের মাধ্যমে বাম বা উপরে সরে গিয়ে (0, 0) এ ফিরে আসা;
- যখন আমরা একটি চেরি সম্বলিত পাথ সেলের মধ্য দিয়ে যাচ্ছি, তখন আমরা এটি তুলে নিই এবং সেলটি একটি খালি ঘরে পরিণত হয় (মান হবে 0);
- যদি (0, 0) এবং (N-1, N-1) এর মধ্যে কোন বৈধ পথ না থাকে, তাহলে কোন চেরি সংগ্রহ করা যাবে না।
সুতরাং, যদি ইনপুট −
এর মত হয়| 0 | 1 | -1 |
| 1 | 0 | -1 |
| 1 | 1 | 1 |
আউটপুট হবে 5, অবস্থান থেকে শুরু করে (0, 0) এবং নিচে, নিচে, ডানদিকে, পৌঁছানোর জন্য (2, 2) চলে গেছে। এখানে এই একক ভ্রমণের সময় 4টি চেরি তোলা হয়েছিল, এবং ম্যাট্রিক্স হয়ে যায়৷
৷| 0 | 1 | -1 |
| 0 | 0 | -1 |
| 0 | 0 | 0 |
তারপর, আমরা বাম দিকে যাব, উপরে, উপরে, বাম দিকে ফিরতে (0,0), আরও একটি চেরি তুলে নিচ্ছি। সংগ্রহ করা চেরির মোট সংখ্যা হবে ৫টি।
এটি সমাধান করতে, আমরা এই পদক্ষেপগুলি অনুসরণ করব -
- আকারের একটি অ্যারে ডিরাইজ সংজ্ঞায়িত করুন:2 x 2 :={{1, 0}, {0, 1}}
- INF :=10^9
- মাপের একটি অ্যারে ডিপি সংজ্ঞায়িত করুন:51 x 51 x 51।
- একটি ফাংশন সল্ভ (), এটি r1, c1, c2, একটি 2D অ্যারে> এবং গ্রিড নেবে,
- n :=গ্রিডের আকার, r2 :=r1 + c1 - c2, ret :=0
- m :=(যদি n অ-শূন্য হয়, তাহলে গ্রিডের আকার[0], অন্যথায় 0)
- যদি r1 <0 বা c1 <0 বা r2 <0 বা c2 <0 বা r1>=n বা r2>=n বা c1>=m বা c2>=m, তাহলে −
- রিটার্ন -INF
- যদি গ্রিড[r1, c1] হয় -1 বা গ্রিড[r2, c2] -1 এর মতো, তাহলে −
- রিটার্ন -INF
- যদি r1 r2 এর সমান হয় এবং c1 হয় c2 এবং r1 n - 1 এবং c1 হয় m - 1 এর সাথে, তাহলে −
- রিটার্ন গ্রিড[r1, c1]
- যদি dp[r1, c1, c2] -1 এর সমান না হয়, তাহলে −
- রিটার্ন dp[r1, c1, c2]
- ret :=ret + গ্রিড[r1, c1]
- যদি r1 r2 এর মত হয় এবং c1 হয় c2 এর মত, তাহলে:কিছুই করবেন না
- অন্যথায়
- ret :=ret + গ্রিড[r2, c2]
- তাপ :=-INF
- আরম্ভ করার জন্য k :=0, যখন k <2, আপডেট করুন (k 1 দ্বারা বৃদ্ধি করুন), −
- করুন
- temp :=সর্বোচ্চ তাপমাত্রা এবং সমাধান (r1 + dir[k, 0], c1 + dir[k, 1], c2 + 1, গ্রিড)
- temp :=সর্বোচ্চ তাপমাত্রা এবং সমাধান (r1 + dir[k, 0], c1 + dir[k, 1], c2, গ্রিড)
- রিটার্ন dp[r1, c1, c2] =ret + temp
- প্রধান পদ্ধতি থেকে, নিম্নলিখিতগুলি করুন -
- -1 দিয়ে dp পূরণ করুন
- ret :=solve(0, 0, 0, grid)
- সর্বোচ্চ রিটার্ন 0 এবং রিটার্ন
আরো ভালোভাবে বোঝার জন্য আসুন নিচের বাস্তবায়ন দেখি -
উদাহরণ
#include <bits/stdc++.h>
using namespace std;
int dir[2][2] = {{1, 0}, {0, 1}};
const int INF = 1e9;
class Solution {
public:
int dp[51][51][51];
int solve(int r1, int c1, int c2, vector < vector <int> >& grid){
int n = grid.size();
int r2 = r1 + c1 - c2;
int ret = 0;
int m = n? grid[0].size() : 0;
if(r1 < 0 || c1 < 0 || r2 < 0 || c2 < 0 || r1 >= n || r2 >= n || c1 >= m || c2 >= m) return -INF;
if(grid[r1][c1] == -1 || grid[r2][c2] == -1) return -INF;
if(r1 == r2 && c1 == c2 && r1 == n - 1 && c1 == m - 1)return grid[r1][c1];
if(dp[r1][c1][c2] != -1) return dp[r1][c1][c2];
ret += grid[r1][c1];
if(r1 == r2 && c1 == c2){
}else ret += grid[r2][c2];
int temp = -INF;
for(int k = 0; k < 2; k++){
temp = max(temp, solve(r1 + dir[k][0], c1 + dir[k][1], c2 + 1, grid));
temp = max(temp, solve(r1 + dir[k][0], c1 + dir[k][1], c2, grid));
}
return dp[r1][c1][c2] = ret + temp;
}
int cherryPickup(vector<vector<int>>& grid) {
memset(dp, -1, sizeof(dp));
int ret = solve(0, 0, 0, grid);
return max(0, ret);
}
};
main(){
Solution ob;
vector<vector<int>> v = {{0,1,-1},{1,0,-1},{1,1,1}};
cout << (ob.cherryPickup(v));
} ইনপুট
{{0,1,-1},{1,0,-1},{1,1,1}} আউটপুট
5
