1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
| // @Title: 黄金矿工 (Path with Maximum Gold)
// @Author: 15816537946@163.com
// @Date: 2022-02-05 23:12:48
// @Runtime: 12 ms
// @Memory: 1.9 MB
var directions = []struct{x,y int}{{1,0},{-1,0},{0,1},{0,-1}}
func getMaximumGold(grid [][]int) int {
var ans int
var dfs func(x, y, gold int)
dfs = func(x,y, gold int) {
gold += grid[x][y]
if gold > ans {
ans = gold
}
rec := grid[x][y]
grid[x][y] = 0
for _, d := range directions {
nx, ny := x+d.x, y+d.y
if nx >=0 && nx<len(grid) && ny >=0 && ny<len(grid[0]) && grid[nx][ny] !=0 {
dfs(nx,ny,gold)
}
}
grid[x][y] = rec
}
for i := range grid {
for j, gold := range grid[i] {
if gold > 0 {
dfs(i,j,0)
}
}
}
return ans
}
|