1219. Path with Maximum Gold
Medium
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, 0
if it is empty.
Return the maximum amount of gold you can collect under the 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
0
gold.You can start and stop collecting gold from any position in the grid that has some gold.
Example 1:
Input: grid = [[0,6,0],[5,8,7],[0,9,0]]
Output: 24
Explanation:
[[0,6,0],
[5,8,7],
[0,9,0]]
Path to get the maximum gold, 9 -> 8 -> 7.
Example 2:
Input: grid = [[1,0,7],[2,0,6],[3,4,5],[0,3,0],[9,0,20]]
Output: 28
Explanation:
[[1,0,7],
[2,0,6],
[3,4,5],
[0,3,0],
[9,0,20]]
Path to get the maximum gold, 1 -> 2 -> 3 -> 4 -> 5 -> 6 -> 7.
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.
解題
func getMaximumGold(grid [][]int) int {
ans := 0
var backtrack func(int, int, int)
backtrack = func(x int, y int, now int) {
// invalid index
if x >= len(grid) || y >= len(grid[0]) || x < 0 || y < 0 {
return
}
// 小於0代表走過了 等於0代表不能走
if grid[x][y] < 0 || grid[x][y] == 0 {
return
}
// 舊的值加上目前這格的值
newValue := now+grid[x][y]
if newValue > ans {
ans = newValue
}
origin := grid[x][y] //因為之後要backtrack,所以改值之前要把原本的存起來
grid[x][y] = -1
backtrack(x+1, y, newValue)
backtrack(x-1, y, newValue)
backtrack(x, y+1, newValue)
backtrack(x, y-1, newValue)
grid[x][y] = origin
}
for i:=0;i<len(grid); i++ {
for j:=0; j<len(grid[0]); j++ {
backtrack(i, j, 0)
}
}
return ans
}
Previous1218. Longest Arithmetic Subsequence of Given DifferenceNext1254. Number of Closed Islands ⭐
Last updated