Đường dẫn với Vàng tối đa trong C ++

Giả sử trong một lưới mỏ vàng có kích thước m * n, mỗi ô trong mỏ này có một số nguyên đại diện cho lượng vàng trong ô đó, 0 có nghĩa là ô trống. Chúng tôi phải tìm số vàng tối đa mà bạn có thể thu thập trong các điều kiện -

Mỗi khi chúng ta chỉ một ô, chúng tôi sẽ thu thập tất cả vàng trong ô đó.
Từ vị trí của mình, chúng ta có thể đi một bước sang trái, phải, lên hoặc xuống.
Chúng tôi không thể truy cập cùng một ô nhiều hơn một lần.
Không bao giờ ghé thăm ô có 0 vàng.

Vì vậy, nếu đầu vào là [[0,6,0], [5,8,7], [0,9,0]], thì kết quả sẽ là 24. Con đường để có được vàng tối đa là 9 -> 8 -> 7

Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -

tạo một phương thức được gọi là dfs, đó là lấy lưới, n, m, i và j. Điều đó sẽ hoạt động như dưới đây
nếu i> =n hoặc j> =m hoặc i <0 hoặc j <0 hoặc lưới [i, j] =-1 hoặc lưới [i, j] =0, thì trả về 0
temp:=grid [i, j], cost:=grid [i, j] và grid [i, j] =-1
chi phí:=chi phí + tối đa của dfs (lưới, n, m, i + 1, j), dfs (lưới, n, m, i - 1, j) và dfs (lưới, n, m, i, j - 1)
grid [i, j]:=temp
chi phí trả lại
phương thức chính sẽ là
n:=các hàng của lưới, m:=các cột của lưới, ans:=0
cho tôi trong phạm vi từ 0 đến n - 1
- cho j trong phạm vi từ 0 đến m - 1
  - nếu grid [i, j] không phải là 0, thì ans:=max of ans, dfs (grid, n, m, i, j)
trả lại ans

Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơn -

Ví dụ

#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));
}

Đầu vào

[[0,6,0],[5,8,7],[0,9,0]]

Đường dẫn với Vàng tối đa trong C ++

Ví dụ

Đầu vào

Đầu ra