黄金矿工

题面

m*n 网格 黄金矿工需要按以下规则来开采黄金，求最大

• 每当矿工进入一个单元，就会收集该单元格中的所有黄金。
• 矿工每次可以从当前位置向上下左右四个方向走。
• 每个单元格只能被开采（进入）一次。
• 不得开采（进入）黄金数目为 0 的单元格。
• 矿工可以从网格中 任意一个 有黄金的单元格出发或者是停止

输入：grid = [[1,0,7],[2,0,6],[3,4,5],[0,3,0],[9,0,20]]
输出：28

解释：

[[1,0,7],
 [2,0,6],
 [3,4,5],
 [0,3,0],
 [9,0,20]]

一种收集最多黄金的路线是：1 -> 2 -> 3 -> 4 -> 5 -> 6 -> 7。

思路

• 每个网格非零值都是值得开挖的起始点
• 每个（存在矿脉的）方格，都有四个方向可选下一步，即四叉树
• 显然相同矿格挖矿之旅只能挖一次，因此需要挖时减计，挖完回填

代码

func getMaximumGold(grid [][]int) int {
    var ans int
    var dig func(int,int, int) int
    rows,cols := len(grid),len(grid[0])
    xy := [4]struct{x,y int}{{0,1},{0,-1},{1,0},{-1,0}} // 方向 右，左，下，上

    dig = func(x,y int, sum int) int {
        if x < 0 || y < 0 || x>=rows || y >=cols || grid[x][y] == 0 {
            return sum 
        }
        t :=grid[x][y]    // t 保存矿脉g[x][y]，便于回溯时候恢复现场
        grid[x][y] = 0
        rs := make([]int,4)
        for i,o := range xy{
            rs[i] = dig(x + o.x,y + o.y,sum + t)
        }
        grid[x][y] = t
        return max(rs...)  // 获取从当前矿点出发能挖的最大矿量
    }

    for i:=0;i<rows;i++ {
        for j:=0;j<cols;j++ {
            if grid[i][j] != 0 {
                if cur := dig(i,j, 0); cur > ans {
                    ans = cur
                }
            }
        }
    }
    return ans
}

func max(vals...int) int {
    var max int
    for _, val := range vals {
        if val > max {
            max = val
        }
    }
    return max
}

本作品采用《CC 协议》，转载必须注明作者和本文链接