Path with Maximum Gold
Problem
In a gold mine grid, walk from any starting cell, picking up its gold and moving up/down/left/right without revisiting cells or stepping on 0-cells. Return the maximum gold you can collect.
grid = [[0,6,0],[5,8,7],[0,9,0]]24def get_maximum_gold(grid):
R, C = len(grid), len(grid[0])
def dfs(r, c):
if r < 0 or r >= R or c < 0 or c >= C or grid[r][c] == 0:
return 0
g = grid[r][c]
grid[r][c] = 0
best = max(dfs(r+1,c), dfs(r-1,c), dfs(r,c+1), dfs(r,c-1))
grid[r][c] = g
return g + best
return max((dfs(r, c) for r in range(R) for c in range(C)), default=0)function getMaximumGold(grid) {
const R = grid.length, C = grid[0].length;
function dfs(r, c) {
if (r < 0 || r >= R || c < 0 || c >= C || grid[r][c] === 0) return 0;
const g = grid[r][c];
grid[r][c] = 0;
const best = Math.max(dfs(r + 1, c), dfs(r - 1, c), dfs(r, c + 1), dfs(r, c - 1));
grid[r][c] = g;
return g + best;
}
let ans = 0;
for (let r = 0; r < R; r++) for (let c = 0; c < C; c++) ans = Math.max(ans, dfs(r, c));
return ans;
}class Solution {
int R, C; int[][] g;
public int getMaximumGold(int[][] grid) {
g = grid; R = grid.length; C = grid[0].length;
int ans = 0;
for (int r = 0; r < R; r++) for (int c = 0; c < C; c++) ans = Math.max(ans, dfs(r, c));
return ans;
}
int dfs(int r, int c) {
if (r < 0 || r >= R || c < 0 || c >= C || g[r][c] == 0) return 0;
int v = g[r][c]; g[r][c] = 0;
int best = Math.max(Math.max(dfs(r+1,c), dfs(r-1,c)), Math.max(dfs(r,c+1), dfs(r,c-1)));
g[r][c] = v;
return v + best;
}
}class Solution {
int R, C;
vector<vector<int>>* gp;
int dfs(int r, int c) {
auto& g = *gp;
if (r < 0 || r >= R || c < 0 || c >= C || g[r][c] == 0) return 0;
int v = g[r][c]; g[r][c] = 0;
int best = max({dfs(r+1,c), dfs(r-1,c), dfs(r,c+1), dfs(r,c-1)});
g[r][c] = v;
return v + best;
}
public:
int getMaximumGold(vector<vector<int>>& grid) {
gp = &grid; R = grid.size(); C = grid[0].size();
int ans = 0;
for (int r = 0; r < R; r++) for (int c = 0; c < C; c++) ans = max(ans, dfs(r, c));
return ans;
}
};Explanation
We want the heaviest path of gold we can walk. Since a path can start anywhere, we simply try starting from every cell and keep the best total we ever collect.
From a starting cell we explore with DFS (depth-first search): pick up the gold here, then recurse into all four neighbors (up, down, left, right) and take the best one. We add that best neighbor result to our own gold and return it.
The key to not revisiting a cell on the same path is a neat backtracking trick: before recursing we set grid[r][c] = 0 so the cell looks empty (and the boundary check skips it), and after recursing we restore it with grid[r][c] = g. This way the cell is blocked only for the current path, and free again for other paths.
Any cell that is already 0 or off the grid returns 0 and stops that branch — there is nothing to collect there.
Example: grid = [[0,6,0],[5,8,7],[0,9,0]]. Starting at the 9, walking to 8, then to 7 gives 9 + 8 + 7 = 24, which is the maximum.