मान लीजिए हमारे पास एक 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) के बीच कोई वैध पथ नहीं है, तो कोई चेरी एकत्र नहीं की जा सकती।
तो, यदि इनपुट इस प्रकार है -
| 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 होगी।
इसे हल करने के लिए, हम निम्न चरणों का पालन करेंगे -
- आकार 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