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 <stdio.h>
2
3int dfs(int** grid, int m, int n, int x, int y) {
4 if (x < 0 || x >= m || y < 0 || y >= n || grid[x][y] == 0)
5 return 0;
6
7 int originalGold = grid[x][y];
8 grid[x][y] = 0; // Mark as visited
9
10 int maxGold = 0;
11 int directions[4][2] = {{1,0}, {-1,0}, {0,1}, {0,-1}};
12 for (int i = 0; i < 4; ++i) {
13 maxGold = fmax(maxGold, dfs(grid, m, n, x + directions[i][0], y + directions[i][1]));
14 }
15
16 grid[x][y] = originalGold; // Backtrack
17 return originalGold + maxGold;
18}
19
20int getMaximumGold(int** grid, int gridSize, int* gridColSize) {
21 int maxGold = 0;
22 for (int i = 0; i < gridSize; ++i) {
23 for (int j = 0; j < gridColSize[i]; ++j) {
24 if (grid[i][j] > 0) {
25 maxGold = fmax(maxGold, dfs(grid, gridSize, gridColSize[i], i, j));
26 }
27 }
28 }
29 return maxGold;
30}The C language implementation uses a recursive function 'dfs' to explore each valid path starting from a gold cell. It employs a grid to mark visited cells by setting their gold value to zero and restores them after backtracking is complete. This way, all potential paths can be explored to determine the path with the maximum gold.
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#include <algorithm>
#include <cstring>
using namespace std;
class Solution {
int dp[1 << 15][15][15];
int dirs[5] = {0, 1, 0, -1, 0};
public:
int solve(vector<vector<int>>& grid, int mask, int x, int y) {
if (dp[mask][x][y] != -1) return dp[mask][x][y];
int maxGold = 0;
for (int d = 0; d < 4; ++d) {
int nx = x + dirs[d], ny = y + dirs[d + 1];
if (nx >= 0 && ny >= 0 && nx < grid.size() && ny < grid[0].size() && grid[nx][ny] > 0
&& !(mask & (1 << (nx * grid[0].size() + ny)))) {
int newMask = mask | (1 << (nx * grid[0].size() + ny));
maxGold = max(maxGold, solve(grid, newMask, nx, ny));
}
}
return dp[mask][x][y] = grid[x][y] + maxGold;
}
int getMaximumGold(vector<vector<int>>& grid) {
memset(dp, -1, sizeof(dp));
int maxGold = 0, m = grid.size(), n = grid[0].size();
for (int i = 0; i < m; ++i) {
for (int j = 0; j < n; ++j) {
if (grid[i][j] > 0) {
int mask = 1 << (i * n + j);
maxGold = max(maxGold, solve(grid, mask, i, j));
}
}
}
return maxGold;
}
};The C++ strategy employs dynamic programming and bit-masking to address cell visted states, similar to the C-underpinning logic. This coverage aims to derive optimal routes leveraging memory efficiently through DP arrays. Referential paths are stored as bitmask iterations with recursive resolution aiding rapid path enumeration.