Path with Maximum Gold
In a gold mine grid of size m x n, each cell in this mine has an integer representing the amount of gold in that cell, or 0 if it is empty.
Return the maximum amount of gold you can collect under the following conditions:
- Every time you are located in a cell, you will collect all the gold in that cell.
- From your position, you can walk one step to the left, right, up, or down.
- You can't visit the same cell more than once.
- Never visit a cell with
0gold. - You can start and stop collecting gold from any position in the grid that has some gold.
Example 1
0 6 0 5 8 7 0 9 0
Input
grid = [[0,6,0],[5,8,7],[0,9,0]]Output
24Path to get the maximum gold is 9 -> 8 -> 7, collecting 24 total gold.
Example 2
1 0 7 2 0 6 3 4 5 0 3 0 9 0 20
Input
grid = [[1,0,7],[2,0,6],[3,4,5],[0,3,0],[9,0,20]]Output
28Path to get the maximum gold is 1 -> 2 -> 3 -> 4 -> 5 -> 6 -> 7, collecting 28 total gold.
Constraints
- m == grid.length
- n == grid[i].length
- 1 <= m, n <= 15
- 0 <= grid[i][j] <= 100
- There are at most 25 cells containing gold.