মনে করুন m * n আকারের একটি সোনার খনির গ্রিডে, এই খনির প্রতিটি ঘরে একটি পূর্ণসংখ্যা রয়েছে যা সেই ঘরে সোনার পরিমাণকে উপস্থাপন করে, 0 মানে খালি। শর্তে আপনি যে সর্বোচ্চ পরিমাণ সোনা সংগ্রহ করতে পারেন তা আমাদের খুঁজে বের করতে হবে −
- যতবার আমরা একটি ঘর নির্দেশ করব আমরা সেই ঘরে সমস্ত সোনা সংগ্রহ করব৷
- আমাদের অবস্থান থেকে আমরা বাম, ডান, উপরে বা নিচে এক ধাপ হাঁটতে পারি।
- আমরা একই কক্ষে একাধিকবার যেতে পারি না।
- কখনও 0 গোল্ড সহ একটি সেল পরিদর্শন করবেন না৷ ৷
সুতরাং ইনপুট যদি [[0,6,0],[5,8,7],[0,9,0]] এর মত হয়, তাহলে ফলাফল হবে 24। সর্বাধিক সোনা পাওয়ার পথ হল 9 -> 8 -> 7
এটি সমাধান করতে, আমরা এই পদক্ষেপগুলি অনুসরণ করব -
- ডিএফএস নামে একটি পদ্ধতি তৈরি করুন, যেটি গ্রিড, n, m, i এবং j গ্রহণ করছে। এটি নিচের মত কাজ করবে
- যদি i>=n বা j>=m বা i<0 বা j <0 বা গ্রিড[i, j] =-1 বা গ্রিড[i, j] =0, তাহলে 0 ফেরত দিন
- temp :=গ্রিড[i, j], খরচ :=গ্রিড[i, j] এবং গ্রিড[i, j] =-1
- খরচ :=খরচ + সর্বাধিক dfs (গ্রিড, n, m, i + 1, j), dfs (গ্রিড, n, m, i – 1, j ) এবং dfs (গ্রিড, n, m, i, j – 1)
- গ্রিড[i, j] :=temp
- ফেরত খরচ
- প্রধান পদ্ধতি হবে
- n :=গ্রিডের সারি, m :=গ্রিডের কলাম, উত্তর :=0
- আমি 0 থেকে n – 1
- পরিসরে j-এর জন্য 0 থেকে m – 1
- যদি গ্রিড[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]]
আউটপুট
24
