Richest Mine Route

MediumBacktracking

Problem

A mine is mapped as a grid grid where each cell holds the amount of gold in it; 0 means the cell is solid rock and cannot be entered.

A miner may start on any gold cell, collects its gold, and moves up, down, left or right to other gold cells, never visiting a cell twice. The miner may stop at any time. Return the maximum gold one route can collect.

Example 1

Input:
grid = [[0, 6, 0], [5, 8, 7], [0, 9, 0]]
Output:
24

9 → 8 → 7 collects 24; no route can reach both 5 and 7 plus 9 without revisiting 8.

Example 2

Input:
grid = [[1, 0, 7], [2, 0, 6], [3, 4, 5], [0, 3, 0], [9, 0, 20]]
Output:
28

1 → 2 → 3 → 4 → 5 → 6 → 7.

Constraints

  • 1 ≤ rows, cols ≤ 15
  • 0 ≤ grid[i][j] ≤ 100
  • At most 25 cells contain gold.

Hint

Show the first hint

There is no obvious greedy rule: you must try routes. From where?

Walkthrough

How to approach it

01Clarify before coding

  • Can the route start and end anywhere? Yes, any gold cell, stop at any time.
  • Can a cell be revisited? No.
  • What if there is no gold? Return 0.

02Brute force

Enumerate every simple path in the whole grid, including through rock, and sum the gold.

Cost: Exponential in the number of cells (up to 225), hopeless. The limit of 25 gold cells is what makes a search over gold cells only viable.

The rest of the walkthrough is in the app

The full walkthrough (key insight, step-by-step, dry run, complexity, edge cases, pitfalls, follow-ups) and solutions in Python and JavaScript are in the app, next to an editor and a terminal that runs your code against the tests.

Solve it in the browserStart free

This problem is part of Pro.