Sponsored
Sponsored
This approach utilizes backtracking and depth-first search (DFS) to explore all possible paths to collect the maximum gold. Start from each cell containing gold and perform DFS to explore in all four possible directions (up, down, left, right). During the search, keep track of the total gold collected. Use backtracking to unvisit a cell after exploring all potential paths from it.
Time complexity: O((m*n)^2) - In the worst-case scenario, each cell containing gold gets visited and backtracked.
Space complexity: O(m*n) - This results from recursive stack space and the grid modifications.
1#include <vector>
2#include <algorithm>
3using namespace std;
4
5class Solution {
6public:
7 int dfs(vector<vector<int>>& grid, int m, int n, int x, int y) {
8 if (x < 0 || x >= m || y < 0 || y >= n || grid[x][y] == 0)
9 return 0;
10
11 int originalGold = grid[x][y];
12 grid[x][y] = 0; // Mark as visited
13 int maxGold = 0;
14 vector<pair<int, int>> directions {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
15 for (auto &dir : directions) {
16 maxGold = max(maxGold, dfs(grid, m, n, x + dir.first, y + dir.second));
17 }
18 grid[x][y] = originalGold; // Backtrack
19 return originalGold + maxGold;
20 }
21
22 int getMaximumGold(vector<vector<int>>& grid) {
23 int maxGold = 0, m = grid.size(), n = grid[0].size();
24 for (int i = 0; i < m; ++i) {
25 for (int j = 0; j < n; ++j) {
26 if (grid[i][j] > 0) {
27 maxGold = max(maxGold, dfs(grid, m, n, i, j));
28 }
29 }
30 }
31 return maxGold;
32 }
33};The C++ version uses a similar DFS approach, utilizing vectors and pair management for movement directions. The structure of the solution ensures a robust search through backtracking, integrating C++ optimization features like STL vectors and max function to enhance efficiency.
This approach involves using dynamic programming with bit masking to track visited states and optimize the path of maximum gold collection. It systematically calculates the maximum gold that can be gathered by starting from each gold cell and considering valid moves while ensuring no cell is revisited.
Time complexity: O(2^(m*n) * m * n) given bitmask state examination.
Space complexity: O(2^(m*n) * m * n) due to DP storage needs for various path states.
1
This implementation uses a bitmask to track visited states and dynamic programming to store interim computations. It only traverses unvisited gold-bearing cells and optimizes path selection for maximal gold collection efficiency. State visits are held in a DP table indexed by the bitmask, with recursive exploration to uncover superior paths.