1219.黄金矿工
1219.黄金矿工
题解
DFS+回溯,貌似大一做过,但是有个坑,见链接
力扣刷题全局变量WA,局部变量AC的问题
代码
package main
var dirs = []struct{ x, y int }{{-1, 0}, {1, 0}, {0, -1}, {0, 1}}
var result int
func getMaximumGold(grid [][]int) int {
var dfs func(x, y, cnt int)
dfs = func(x, y, cnt int) {
cnt += grid[x][y]
if cnt > result {
result = cnt
}
res := grid[x][y]
grid[x][y] = 0
for _, v := range dirs {
nowX := x + v.x
nowY := y + v.y
if nowX >= 0 && nowX < len(grid) && nowY >= 0 && nowY < len(grid[0]) && grid[nowX][nowY] > 0 {
dfs(nowX, nowY, cnt)
}
}
grid[x][y] = res
}
for i, v := range grid {
for j, vv := range v {
if vv > 0 {
dfs(i, j, 0)
}
}
}
defer func() {
result = 0
}()
return result
}