Code Implementation

class Solution:
    def getMaximumGold(self, grid):
        rows, cols = len(grid), len(grid[0])
        res = 0

        def dfs(x, y, total):
            nonlocal res
            gold = grid[x][y]
            res = max(res, total + gold)
            grid[x][y] = 0  # Mark as visited
            for dx, dy in [(-1,0),(1,0),(0,-1),(0,1)]:
                nx, ny = x + dx, y + dy
                if 0 <= nx < rows and 0 <= ny < cols and grid[nx][ny] > 0:
                    dfs(nx, ny, total + gold)
            grid[x][y] = gold  # Backtrack

        for i in range(rows):
            for j in range(cols):
                if grid[i][j] > 0:
                    dfs(i, j, 0)
        return res
      

class Solution {
public:
    int getMaximumGold(vector<vector<int>>& grid) {
        int res = 0, rows = grid.size(), cols = grid[0].size();
        function<void(int,int,int)> dfs = [&](int x, int y, int total) {
            int gold = grid[x][y];
            res = max(res, total + gold);
            grid[x][y] = 0;
            vector<pair<int,int>> dirs = {{-1,0},{1,0},{0,-1},{0,1}};
            for (auto [dx,dy]: dirs) {
                int nx = x + dx, ny = y + dy;
                if (nx >= 0 && nx < rows && ny >= 0 && ny < cols && grid[nx][ny] > 0)
                    dfs(nx, ny, total + gold);
            }
            grid[x][y] = gold;
        };
        for (int i = 0; i < rows; ++i)
            for (int j = 0; j < cols; ++j)
                if (grid[i][j] > 0)
                    dfs(i, j, 0);
        return res;
    }
};
      

class Solution {
    int res = 0, rows, cols;
    public int getMaximumGold(int[][] grid) {
        rows = grid.length; cols = grid[0].length;
        for (int i = 0; i < rows; i++)
            for (int j = 0; j < cols; j++)
                if (grid[i][j] > 0)
                    dfs(grid, i, j, 0);
        return res;
    }
    void dfs(int[][] grid, int x, int y, int total) {
        int gold = grid[x][y];
        res = Math.max(res, total + gold);
        grid[x][y] = 0;
        int[] dx = {-1,1,0,0}, dy = {0,0,-1,1};
        for (int d = 0; d < 4; d++) {
            int nx = x + dx[d], ny = y + dy[d];
            if (nx >= 0 && nx < rows && ny >= 0 && ny < cols && grid[nx][ny] > 0)
                dfs(grid, nx, ny, total + gold);
        }
        grid[x][y] = gold;
    }
}
      

var getMaximumGold = function(grid) {
    let res = 0, rows = grid.length, cols = grid[0].length;
    function dfs(x, y, total) {
        let gold = grid[x][y];
        res = Math.max(res, total + gold);
        grid[x][y] = 0;
        for (let [dx, dy] of [[-1,0],[1,0],[0,-1],[0,1]]) {
            let nx = x + dx, ny = y + dy;
            if (nx >= 0 && nx < rows && ny >= 0 && ny < cols && grid[nx][ny] > 0)
                dfs(nx, ny, total + gold);
        }
        grid[x][y] = gold;
    }
    for (let i = 0; i < rows; i++)
        for (let j = 0; j < cols; j++)
            if (grid[i][j] > 0)
                dfs(i, j, 0);
    return res;
};
      

Problem Description

You are given a 2D grid representing a gold mine. Each cell in the grid contains an integer indicating the amount of gold present, or zero if there is none.
Your goal is to collect as much gold as possible by moving from one cell to another. The rules are:

• You can start and stop collecting gold from any cell with non-zero gold.
• You may move up, down, left, or right to adjacent cells.
• You cannot visit the same cell more than once in a single path.
• You cannot move to a cell with zero gold.

• Each cell can be used at most once per path.
• You can start from any non-zero cell.
• There may be multiple disconnected gold regions.

Thought Process

When approaching this problem, the first idea might be to try every possible path starting from every gold cell and keep track of the maximum gold collected. This brute-force approach is feasible because the grid is small (at most 25x25), but we want to make it as efficient as possible.

The challenge is to avoid revisiting cells and to ensure we only move to adjacent gold-containing cells. Since we can start from any gold cell, we must consider all possible starting points.

The problem is similar to finding the "maximum path sum" in a graph where each node is a gold cell and edges connect adjacent gold cells. A depth-first search (DFS) is a natural fit for exploring all possible paths, as it allows us to mark cells as visited and backtrack efficiently.

We also realize that since we can start from any gold cell, we need to try a DFS from each one. The key optimization is to use in-place marking (temporarily setting the cell to 0) to avoid extra memory usage for visited flags, and to backtrack (restore the value) after each path.

Solution Approach

Let's break down the solution step by step:

1. Iterate Over All Cells:
   For every cell in the grid, if it contains gold (value > 0), start a DFS from that cell.
2. DFS Traversal:
   Use depth-first search to explore all possible paths from the current cell. At each step:
   • Mark the current cell as visited (set it to 0).
   • Try moving in all four directions (up, down, left, right).
   • If the adjacent cell contains gold and hasn't been visited, recurse into that cell.
   • After exploring, backtrack by restoring the original gold value.
3. Track Maximum Gold:
   Keep a global or external variable to track the maximum amount of gold collected along any path.
4. Return the Result:
   After all DFS explorations, return the maximum gold collected.

• DFS is ideal for exploring all possible paths without revisiting cells.
• In-place marking saves space and makes backtracking straightforward.
• The grid's small size ensures DFS won't hit stack or performance limits.

Example Walkthrough

Let's consider the following grid:

      [ [0, 6, 0],
        [5, 8, 7],
        [0, 9, 0] ]
    

1. Start at cell (1,1) with 8 gold.
   • Move left to (1,0): +5 (total 13)
   • Backtrack, move right to (1,2): +7 (total 15)
   • From (1,2), move up to (0,1): +6 (total 21)
   • From (1,1), move down to (2,1): +9 (total 17)
2. Try starting from other gold cells (e.g., (2,1)), but no path yields more than 24.
3. The best path is: (2,1) → (1,1) → (1,2) → (0,1), collecting 9+8+7+6 = 30.

Time and Space Complexity

Brute-force:

• For each gold cell, try all possible paths (exponential in the number of gold cells).
• Time: O(k * 4^k), where k is the number of gold cells (since each cell can branch in up to 4 directions).
• Space: O(k) for the recursion stack and possibly visited markers.

• Still explores all paths, but in-place marking and early pruning (can't visit zero or out-of-bounds) help.
• Time: Still O(k * 4^k) in the worst case, but practical due to small grid size (k ≤ 25*25).
• Space: O(k) for recursion stack (at most as deep as the number of gold cells in a path).

• The constraints guarantee that k is small, making this approach feasible.

Summary

This problem is a classic example of using depth-first search with backtracking to explore all possible paths in a grid while avoiding revisiting cells. By starting DFS from every gold cell, marking cells as visited in-place, and backtracking, we ensure every potential path is checked. The approach is efficient due to the small grid size, and the solution elegantly leverages recursion and careful state management to find the maximum gold path.