C ++中具有最大金数的路径

假设在大小为m * n的金矿网格中，该矿中的每个单元格都有一个整数，表示该单元格中的金含量，0表示为空。我们必须找到在以下条件下可以收集的最大数量的黄金-

• 每次我们指向一个单元格时，我们都会收集该单元格中的所有黄金。

• 从我们的位置，我们可以向左，向右，向上或向下走一步。

• 我们不能多次访问同一个单元。

• 切勿访问0金的单元格。

因此，如果输入类似于[[0,6,0]，[5,8,7]，[0,9,0]]，则结果将为24。获得最大黄金的路径为9-> 8 -> 7

为了解决这个问题，我们将遵循以下步骤-

• 制作一个称为dfs的方法，即采用格网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]，成本：= grid [i，j] and grid [i，j] = -1

• cost：=成本+ dfs（grid，n，m，i + 1，j），dfs（grid，n，m，i – 1，j）和dfs（grid，n，m，i，j – 1的最大值） ）

• grid [i，j]：=温度

• 返回成本

• 主要方法是

• n：=网格行，m：=网格列，ans：= 0

• 对于i，范围为0至n – 1

• 如果grid [i，j]不为0，则ans：= max of 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]){
               //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