C++에서 최대 골드가 있는 경로

<시간/>

m * n 크기의 금광 그리드에서 이 광산의 각 셀에 해당 셀의 금 양을 나타내는 정수가 있다고 가정합니다. 0은 비어 있음을 의미합니다. 다음 조건에서 수집할 수 있는 최대 골드 양을 찾아야 합니다. -

셀을 가리킬 때마다 해당 셀에 있는 모든 금을 수집합니다.
자신의 위치에서 왼쪽, 오른쪽, 위 또는 아래로 한 걸음 걸을 수 있습니다.
같은 셀을 두 번 이상 방문할 수 없습니다.
골드가 0인 방은 절대 방문하지 마세요.

따라서 입력이 [[0,6,0],[5,8,7],[0,9,0]]과 같으면 결과는 24가 됩니다. 최대 골드를 얻는 경로는 9 -> 8입니다. -> 7

이 문제를 해결하기 위해 다음 단계를 따릅니다. −

그리드, n, m, i 및 j를 사용하는 dfs라는 메서드를 하나 만듭니다. 아래와 같이 작동합니다.
i>=n 또는 j>=m 또는 i<0 또는 j <0 또는 grid[i, j] =-1 또는 grid[i, j] =0이면 0을 반환합니다.
temp :=grid[i, j], 비용 :=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)
그리드[i, j] :=임시
반품 비용
주요 방법은
n :=그리드의 행, m :=그리드의 열, ans :=0
0 ~ n – 1 범위의 i에 대해
- 0 ~ m – 1 범위의 j에 대해
  - 그리드[i, j]가 0이 아니면 ans :=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]]

C++에서 최대 골드가 있는 경로

예

입력

출력