⚡Flashcard Drill➔
NeetCode #602LC-1219MediumGraphs
← Back to All Problems

#602 · #1219 · Path with Maximum Gold(黄金矿工)

📌 Problem Statement & Constraints

In a gold mine grid, each cell holds a non-negative amount of gold; 0 means an obstacle. Starting anywhere, you may move in the four cardinal directions but cannot revisit a cell, and cannot enter a 0. Return the maximum gold you can collect. Constraints: 1 <= m, n <= 15, 0 <= grid[i][j] <= 100.

💡 Core Algorithmic Approaches

  1. This is a DFS with backtracking: the path must be simple, so cells are marked and unmarked.
  2. From every non-zero cell, explore all four directions, accumulating the gold.
  3. The maximum is tracked at every step (not just at dead ends), since stopping anywhere is allowed.
  4. The grid is at most 15x15, so the exhaustive search is feasible.

💻 Benchmark Python3 Implementation

class Solution:
    def getMaximumGold(self, grid: List[List[int]]) -> int:
        m, n = len(grid), len(grid[0])
        self.best = 0

        def dfs(r: int, c: int, total: int) -> None:
            if not (0 <= r < m and 0 <= c < n) or grid[r][c] == 0:
                return
            gold = grid[r][c]
            grid[r][c] = 0                 # mark as used (cannot revisit)
            total += gold
            self.best = max(self.best, total)   # stopping here is allowed
            for dr, dc in ((0, 1), (0, -1), (1, 0), (-1, 0)):
                dfs(r + dr, c + dc, total)
            grid[r][c] = gold              # backtrack

        for i in range(m):
            for j in range(n):
                if grid[i][j]:
                    dfs(i, j, 0)
        return self.best

⚡ Complexity Deep Dive

⏱️ Time Complexity
O(m * n * 4^(m*n)) worst case, heavily pruned by the obstacle cells.
💾 Space Complexity
O(m * n) for the recursion depth.

⚠️ Interview Pitfalls & Follow-ups

  • Only updating the best at dead ends: the path may stop early, so every node is a candidate.
  • Forgetting to restore the cell on backtrack: other starting points would see a modified grid.
  • Allowing revisits: the problem forbids them.
  • Treating 0 as collectible: it is an obstacle.
⚡
Test muscle memory on this topic via 3-Layer Flashcards
Active Recall: Mentally formulate Prompt ➔ Math Derivation ➔ Benchmark Implementation in 3 minutes.
🎯 Drill This Card Now➔

🧩 Related Graphs Problems