मान लीजिए m * n आकार की एक सोने की खदान ग्रिड है, इस खदान में प्रत्येक सेल में एक पूर्णांक है जो उस सेल में सोने की मात्रा दर्शाता है, 0 का अर्थ है खाली। हमें निम्नलिखित शर्तों के तहत एकत्र किए जा सकने वाले सोने की अधिकतम मात्रा ढूंढनी है:
- हर बार जब हम एक सेल पर होते हैं, हम उस सेल का सारा सोना एकत्र करते हैं।
- हमारी स्थिति से हम बाएं, दाएं, ऊपर या नीचे एक कदम चल सकते हैं।
- हम एक ही सेल को एक से अधिक बार नहीं देख सकते।
- कभी भी 0 सोने वाले सेल पर न जाएं।
उदाहरण के लिए, यदि इनपुट [[0,6,0],[5,8,7],[0,9,0]] है, तो परिणाम 24 होगा। अधिकतम सोना पाने का पथ 9 -> 8 -> 7 है।
हल करने के चरण
- dfs नामक एक विधि बनाएं, जो grid, n, m, i और j लेती है
- यदि i >= n या j >= m या i<0 या j<0 या grid[i][j] = -1 या grid[i][j] = 0, तो 0 वापस करें
- temp := grid[i][j], cost := grid[i][j] और grid[i][j] = -1
- cost := cost + max(dfs(grid,n,m,i+1,j), dfs(grid,n,m,i-1,j), dfs(grid,n,m,i,j-1), dfs(grid,n,m,i,j+1))
- grid[i][j] := temp
- cost वापस करें
- मुख्य विधि:
- n := grid की पंक्तियां, m := grid के स्तंभ, ans := 0
- i को 0 से n-1 तक लूप करें
- j को 0 से m-1 तक लूप करें
- यदि grid[i][j] 0 नहीं है, तो ans := max(ans, dfs(grid,n,m,i,j))
- j को 0 से m-1 तक लूप करें
- ans वापस करें
उदाहरण
#include <bits/stdc++.h> using namespace std; class Solution { public: int dfs(vector<vector<int>>& grid, int n, int m, int i, int j){ if(i>=n || j>=m ||i<0||j<0 || grid[i][j]==-1 || grid[i][j] == 0)return 0; int temp =grid[i][j]; int cost = grid[i][j]; grid[i][j] = -1; cost+=max({dfs(grid,n,m,i+1,j),dfs(grid,n,m,i-1,j),dfs(grid,n,m,i,j+1),dfs(grid,n,m,i,j-1)}); grid[i][j] = temp; return cost; } int getMaximumGold(vector<vector<int>>& grid) { int n = grid.size() ; int m = grid[0].size(); int ans = 0; for(int i =0;i<n;i++){ for(int j =0;j<m;j++){ if(grid[i][j]){ ans = max(ans,dfs(grid,n,m,i,j)); } } } return ans; } }; main(){ vector<vector<int>> v = {{0,6,0},{5,8,7},{0,9,0}}; Solution ob; cout << (ob.getMaximumGold(v)); }इनपुट
[[0,6,0],[5,8,7],[0,9,0]]
आउटपुट
24
