सी++ में चेरी पिकअप

मान लीजिए हमारे पास एक एन एक्स एन ग्रिड है, यह चेरी से भरा है। प्रत्येक सेल में निम्न में से एक संभावित पूर्णांक होता है -

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) जाएंगे। उठाए गए चेरी की कुल संख्या 5 होगी।

इसे हल करने के लिए, हम इन चरणों का पालन करेंगे -

आकार की एक सरणी dir परिभाषित करें:2 x 2 :={{1, 0}, {0, 1}}
आईएनएफ:=10^9
एक सरणी dp आकार परिभाषित करें: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 के बराबर नहीं है, तो −
- रिटर्न डीपी[r1, c1, c2]
ret :=ret + grid[r1, c1]
यदि r1 r2 के समान है और c1 c2 के समान है, तो:कुछ न करें
अन्यथा
- ret:=ret + grid[r2, c2]
अस्थायी:=-INF
इनिशियलाइज़ k :=0 के लिए, जब k <2, अपडेट करें (k को 1 से बढ़ाएँ), −
- अस्थायी:=अधिकतम अस्थायी और हल(r1 + dir[k, 0], c1 + dir[k, 1], c2 + 1, ग्रिड)
- अस्थायी:=अधिकतम अस्थायी और हल (r1 + dir[k, 0], c1 + dir[k, 1], c2, ग्रिड)
रिटर्न dp[r1, c1, c2] =ret + temp
मुख्य विधि से, निम्न कार्य करें -
dp को -1 से भरें
रिट:=हल करें(0, 0, 0, ग्रिड)
अधिकतम 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}}