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]andgrid[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:=maxofans,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