Computer >> कंप्यूटर ट्यूटोरियल >  >> प्रोग्रामिंग >> C++

C++ में चेरी पिकअप (Cherry Pickup)


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

  • 0 - इंगित करता है कि सेल खाली है, इसलिए हम इसके माध्यम से गुजर सकते हैं
  • 1 - इंगित करता है कि सेल में एक चेरी है, जिसे हम उठा सकते हैं और इसके माध्यम से गुजर सकते हैं
  • -1 - इंगित करता है कि सेल में एक कांटा (thorn) है जो रास्ता रोकता है

हमें इन कुछ नियमों का उपयोग करके अधिकतम संख्या में चेरी एकत्र करनी हैं -

  • स्थिति (0, 0) से शुरू करें और (N-1, N-1) पर समाप्त करें, वैध पथ सेलों के माध्यम से दाएं या नीचे जाकर
  • सेल (N-1, N-1) तक पहुंचने के बाद, वैध पथ सेलों के माध्यम से बाएं या ऊपर जाकर (0, 0) पर वापस लौटें;
  • जब हम एक पथ सेल से गुजरते हैं जिसमें चेरी होती है, तो हम इसे उठा लेते हैं और सेल खाली सेल बन जाता है (मान 0 होगा);
  • यदि (0, 0) और (N-1, N-1) के बीच कोई वैध पथ नहीं है, तो कोई चेरी एकत्र नहीं की जा सकती।

तो, यदि इनपुट इस प्रकार है -

01-1
10-1
111

आउटपुट 5 होगा, क्योंकि स्थिति (0, 0) से शुरू करके नीचे, नीचे, दाएं, दाएं जाकर (2, 2) तक पहुंचे। यहां इस एकल यात्रा के दौरान 4 चेरी उठाई गईं, और मैट्रिक्स बन जाता है।

01-1
00-1
000

फिर, हम बाएं, ऊपर, ऊपर, बाएं जाकर (0,0) पर वापस लौटेंगे, एक और चेरी उठाते हुए। उठाई गई चेरी की कुल संख्या 5 होगी।

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

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

  1. - C++ में Switch स्टेटमेंट: एक पूर्ण गाइड

    C++ में Switch स्टेटमेंट का उपयोग कैसे करें कंडीशनल स्टेटमेंट्स सभी प्रोग्रामिंग भाषाओं की एक सामान्य विशेषता हैं। इन स्टेटमेंट्स का उपयोग प्रोग्राम के प्रवाह को नियंत्रित करने और यह निर्दिष्ट करने के लिए किया जाता है कि कोड के विशिष्ट ब्लॉक्स कब निष्पादित होने चाहिए। C++ में उपयोग किए जाने वाले मुख

  1. - C++ में मितव्ययी संख्या (Frugal Number)

    इस समस्या में, हमें एक धनात्मक पूर्णांक N दिया गया है। हमारा कार्य यह जांचने के लिए एक प्रोग्राम बनाना है कि दी गई संख्या मितव्ययी संख्या है या नहीं। मितव्ययी संख्या (FRUGAL NUMBER) − एक संख्या जिसके अंकों की संख्या उस संख्या के अभाज्य गुणनखंडन में अंकों की संख्या से सख्ती से अधिक है। उदाहरण &

  1. C++ में पेंटाटोप संख्या C++ में पेंटाटोप संख्या

    एक पेंटाटोप संख्या को पास्कल के त्रिभुज में पांचवीं संख्या के रूप में वर्णित किया गया है। अब, चूंकि यह पांचवीं संख्या है, इसका मतलब है कि पास्कल के त्रिभुज में कम से कम पांच संख्याएं होनी चाहिए, इसलिए इस श्रृंखला की पहली संख्या 1 4 6 4 1 से शुरू होती है जो पास्कल के त्रिभुज की चौथी पंक्ति है। तो, इस