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