622. Gold Mine Walk
A miner enters a rectangular cave drawn as the matrix grid. Each entry is the amount of gold in that cell, and 0 marks solid rock that cannot be entered. The miner may start at any cell that contains gold, collects everything in the cell, and then repeatedly steps to a neighbouring cell (up, down, left or right) that still has gold. A cell can be visited at most once, so the gold of a cell is taken only one time. The miner may stop at any moment.
Return the largest total amount of gold the miner can collect.
Example 1
- Input:
- grid = [[2,0,9],[4,6,0],[0,5,3]]
- Output:
- 20
- Explanation:
Start at 2, go down to 4, right to 6, down to 5 and right to 3: 2 + 4 + 6 + 5 + 3 = 20. The 9 is cut off by rock, so it can only be collected alone.
Example 2
- Input:
- grid = [[7]]
- Output:
- 7
- Explanation:
A single cell is both start and end.
Example 3
- Input:
- grid = [[0,0],[0,0]]
- Output:
- 0
- Explanation:
The cave contains no gold, so the miner collects nothing.
Constraints
- 1 ≤
grid.length,grid[i].length≤ 5 - 0 ≤
grid[i][j]≤ 100 - At most 15 cells contain gold.
How this problem is judged
- Answers
- Your answer must match exactly. Numbers compare by value, so 2 and 2.0 are equal.
Expected complexity
- Time
- O(g * 3^g)
- Space
- O(g)