একটি m×n গ্রিডে প্রতিটি সেলে সোনার পরিমাণ দেওয়া। ০ মানে খালি। আপ-ডাউন-লেফট-রাইট ঘুরে সর্বোচ্চ সোনা সংগ্রহ করতে হবে, শর্ত: একই সেল دوبার যাবেন না, ০ ভ্যালুয়াল সেলে যাবেন না।
উদাহরণ: [[0,6,0],[5,8,7],[0,9,0]] → ২৪ (পাথ: 9→8→7)।
সমাধানের ধাপসমূহ
- প্রতিটি নন-জিরো সেল থেকে DFS চালান।
- ভিজিট করা সেলকে -1 দিয়ে মার্ক করুন, ব্যাকট্র্যাকিং সময় ফিরিয়ে দিন।
- ৪ ডিরেকশনে রিকার্সিভ কল করুন এবং ম্যাক্সিমাম নিন।
- গ্লোবাল ম্যাক্স আপডেট করুন।
C++ উদাহরণ
#include <bits/stdc++.h>
using namespace std;
class Solution {
int dfs(vector<vector<int>>& grid, int n, int m, int i, int j) {
if (i < 0 || i >= n || j < 0 || j >= m || grid[i][j] == 0 || grid[i][j] == -1) return 0;
int gold = grid[i][j];
grid[i][j] = -1; // mark visited
int best = 0;
best = max(best, dfs(grid, n, m, i+1, j));
best = max(best, dfs(grid, n, m, i-1, j));
best = max(best, dfs(grid, n, m, i, j+1));
best = max(best, dfs(grid, n, m, i, j-1));
grid[i][j] = gold; // restore
return gold + best;
}
public:
int getMaximumGold(vector<vector<int>>& grid) {
int n = grid.size(), m = grid[0].size(), ans = 0;
for (int i = 0; i < n; i++)
for (int j = 0; j < m; j++)
if (grid[i][j]) ans = max(ans, dfs(grid, n, m, i, j));
return ans;
}
};
int 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
