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