C++で最大のゴールドを持つパス

サイズm*nの金鉱山グリッドで、この鉱山の各セルに、そのセル内の金の量を表す整数があるとします。0は空であることを意味します。条件の下で収集できる金の最大量を見つける必要があります-

• セルを指すたびに、そのセル内のすべての金を収集します。
• 私たちの位置から、左、右、上、または下に一歩歩くことができます。
• 同じセルに複数回アクセスすることはできません。
• ゴールドが0のセルには絶対にアクセスしないでください。

したがって、入力が[[0,6,0]、[5,8,7]、[0,9,0]]の場合、結果は24になります。最大のゴールドを取得するためのパスは9->8です。 -> 7

これを解決するには、次の手順に従います-

• dfsと呼ばれる1つのメソッドを作成します。これは、grid、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]、cost：=grid [i、j]およびgrid [i、j] =-1
• コスト：=コスト+ dfs（grid、n、m、i + 1、j）、dfs（grid、n、m、i – 1、j）およびdfs（grid、n、m、i、 j – 1）
• grid [i、j]：=temp
• 返品費用
• 主な方法は
• n：=グリッドの行、m：=グリッドの列、ans：=0
• 0からn–1の範囲のiの場合
  • 0からm–1の範囲のjの場合
    • grid [i、j]が0でない場合、ans：=max of ans、dfs（grid、n、m、i、j）
• 回答を返す

理解を深めるために、次の実装を見てみましょう-

例

#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