মনে করুন, একটি N x N গ্রিড আছে যা চেরি দিয়ে ভরা। প্রতিটি সেলে নিচের পূর্ণসংখ্যাগুলোর যেকোনো একটি থাকতে পারে:
- ০ — সেলটি খালি, যাওয়া যায়
- ১ — সেলে চেরি আছে, সংগ্রহ করে যাওয়া যায়
- -১ — সেলে কাঁটা আছে, পথ বন্ধ
আমাদের নিচের নিয়ম মেনে সর্বাধিক চেরি সংগ্রহ করতে হবে:
- (0, 0) থেকে (N-1, N-1) পর্যন্ত ডান বা নিচে যাওয়া
- (N-1, N-1) থেকে (0, 0) পর্যন্ত বাম বা উপরে ফিরে আসা
- চেরি যাবেন সেলটি খালি হয়ে যাবে (০ হয়ে যাবে)
- যদি (0,0) এবং (N-1,N-1) এর মধ্যে কোনো বৈধ পথ না থাকে, তবে চেরি সংগ্রহ করা যাবে না
সমাধানের ধাপসমূহ
- দিক নির্দেশক অ্যারে dir := {{1,0}, {0,1}}
- INF := 10^9
- 51 x 51 x 51 আকারের dp অ্যারে সংজ্ঞায়িত করুন
- solve() ফাংশন সংজ্ঞায়িত করুন: r1, c1, c2, grid
- n := grid.size(), r2 := r1 + c1 - c2
- বৈধতা চেক: বাউন্ডের বাইরে বা কাঁটা থাকলে -INF রিটার্ন
- গন্তব্যে পৌঁছালে grid[r1][c1] রিটার্ন
- যদি dp[r1][c1][c2] != -1 হয়, সেটি রিটার্ন
- ret := grid[r1][c1] + (r1!=r2 || c1!=c2 ? grid[r2][c2] : 0)
- temp := -INF
- k := 0,1 জন্য temp = max(temp, solve(...))
- dp[r1][c1][c2] = ret + temp রিটার্ন
- মূল ফাংশন: dp -1 দিয়ে ভরুন, solve(0,0,0,grid) কল করুন, max(0, ret) রিটার্ন
উদাহরণ
#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
