The richest walk through a mine
grid[i][j] is the amount of gold in a cell of a mine, or 0 where solid rock blocks the way.
A miner starts in any cell that holds gold and moves one cell up, down, left or right at a time. They never step into a 0 cell, never visit a cell twice, and may stop whenever they like. They collect all the gold in every cell they visit.
Return the most gold one walk can collect.
- Input
grid = [[4,0,3],[5,1,0],[0,2,9]]- Output
21
Walk 4, 5, 1, 2, 9. The 3 is walled off by rock on both sides.
- Input
grid = [[0,0],[0,0]]- Output
0
There is no gold, so there is no walk to take.
Limits
1 <= m, n <= 150 <= grid[i][j] <= 100at most 20 cells hold gold
Hints
Hint 1
From every gold cell, try every walk: step into a neighbour, carry on from there, then step back and try the next direction.
Hint 2
Mark a cell as used while the walk stands on it (set it to 0) and put its gold back when you step out, so other walks can use it.
Where this was reported
Our own problem on the task these candidates describe; the wording, examples and tests are InternDoor’s.
Run your code to check it on the examples. Submit runs every hidden test.
