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
}