C++ में अधिकतम स्वर्ण के साथ पथ

मान लीजिए कि m * n आकार की सोने की खान ग्रिड में, इस खदान में प्रत्येक सेल में एक पूर्णांक है जो उस सेल में सोने की मात्रा का प्रतिनिधित्व करता है, 0 का मतलब है कि खाली है। हमें अधिकतम मात्रा में सोना खोजना होगा जिसे आप शर्तों के तहत एकत्र कर सकते हैं -

• हर बार जब हम किसी सेल की ओर इशारा करते हैं तो हम उस सेल का सारा सोना इकट्ठा कर लेते हैं।
• अपनी स्थिति से हम एक कदम बाएं, दाएं, ऊपर या नीचे चल सकते हैं।
• हम एक ही सेल में एक से अधिक बार नहीं जा सकते।
• कभी भी 0 गोल्ड वाले सेल में न जाएं।

तो अगर इनपुट [[0,6,0], [5,8,7], [0,9,0]] जैसा है, तो परिणाम 24 होगा। अधिकतम सोना प्राप्त करने का मार्ग 9 -> 8 है -> 7

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

• डीएफएस नामक एक विधि बनाएं, जो ग्रिड, एन, एम, आई और जे ले रही है। यह नीचे की तरह कार्य करेगा
• अगर i>=n या j>=m या i<0 या j <0 या ग्रिड[i, j] =-1 या ग्रिड[i, j] =0, तो वापस 0
• अस्थायी:=ग्रिड[i, j], लागत:=ग्रिड[i, j] और ग्रिड[i, j] =-1
• लागत:=लागत + अधिकतम dfs (ग्रिड, n, m, i + 1, j), dfs (ग्रिड, n, m, i – 1, j) और dfs (ग्रिड, n, m, i, जे - 1)
• ग्रिड[i, j] :=अस्थायी
• वापसी लागत
• मुख्य विधि होगी
• n :=ग्रिड की पंक्तियाँ, m :=ग्रिड के स्तंभ, उत्तर :=0
• मैं के लिए 0 से n - 1 की सीमा में
  • जे के लिए 0 से मी - 1 की सीमा में
    • यदि ग्रिड [i, j] 0 नहीं है, तो उत्तर:=अधिकतम उत्तर, dfs (ग्रिड, n, m, i, j)
• वापसी उत्तर

आइए बेहतर समझ पाने के लिए निम्नलिखित कार्यान्वयन देखें -

उदाहरण

#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]){
               //cout << "Start : " << i <<" " << j << endl;
               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