เส้นทางที่มีทองสูงสุดใน C++

สมมติว่าในตารางเหมืองทองคำขนาด m * n แต่ละเซลล์ในเหมืองนี้มีจำนวนเต็มซึ่งแทนปริมาณทองคำในเซลล์นั้น 0 หมายความว่าว่างเปล่า เราต้องหาจำนวนทองคำสูงสุดที่คุณสามารถรวบรวมได้ภายใต้เงื่อนไข -

• ทุกครั้งที่เราชี้เซลล์ เราจะรวบรวมทองคำทั้งหมดในห้องนั้น
• จากตำแหน่งของเรา เราสามารถเดินไปทางซ้าย ขวา ขึ้นหรือลงได้หนึ่งก้าว
• เราไม่สามารถไปที่เซลล์เดียวกันได้มากกว่าหนึ่งครั้ง
• อย่าไปเยี่ยมเซลล์ที่มี 0 ทอง

ดังนั้นหากอินพุตเป็น [[0,6,0],[5,8,7],[0,9,0]] ผลลัพธ์จะเป็น 24 เส้นทางที่จะได้รับทองสูงสุดคือ 9 -> 8 -> 7

เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้ -

• สร้างเมธอดเดียวที่เรียกว่า dfs ซึ่งใช้ 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(กริด, n, m, i + 1, j), dfs(กริด, n, m, i – 1, j ) และ dfs(กริด, n, m, i, เจ – 1)
• grid[i, j] :=อุณหภูมิ
• ค่าส่งคืน
• วิธีหลักจะเป็น
• n :=แถวของตาราง m :=คอลัมน์ของตาราง ans :=0
• สำหรับ i ในช่วง 0 ถึง n – 1
  • สำหรับ j ในช่วง 0 ถึง m – 1
    • ถ้า 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