假设在大小为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
