leetcode 1219 黄金矿工问题

Question

题目描述

原题描述为：传送门
你要开发一座金矿，地质勘测学家已经探明了这座金矿中的资源分布，并用大小为 m * n 的网格 grid 进行了标注。每个单元格中的整数就表示这一单元格中的黄金数量；如果该单元格是空的，那么就是 0。

为了使收益最大化，矿工需要按以下规则来开采黄金：

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

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/probl...
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

题目来源及自己的思路

本题目来自leetcode 第1219题，黄金矿工问题
我自己的思路是深度优先遍历， 找到最大值

相关代码

/**
 * @param {number[][]} grid
 * @return {number}
 */
var getMaximumGold = function(grid) {
    return handle(grid)
};
function handle (grid) {
    var v = grid.length
    var h = grid.length === 0 ? 0 : grid[0].length
    
    // 存储结果
    var arr = [] 
    
    // 初始化标记数组
    var flagArr = new Array(v)
    
    for (let i = 0;i < v;i++) {
        for (let j = 0;j < h;j++) {
            if (grid[i][j] !== 0) {
                // 每次开始前先把标记数组置为0
                for(let k = 0;k < v;k++) {
                  flagArr[k] = new Array(h).fill(0)
                }
                arr.push(dfs(grid, i, j, v, h, flagArr)) 
            }
        }
    }
    return arr.sort((a, b) => b - a)[0]
}

function dfs (grid, i, j, v, h, flagArr) {
    if (i >= 0 && i < v && j >= 0 && j < h && grid[i][j] !== 0 && flagArr[i][j] === 0) {
        flagArr[i][j] = 1
        return grid[i][j] + Math.max(Math.max(Math.max(dfs(grid, i - 1, j, v, h, flagArr), dfs(grid, i + 1, j, v, h, flagArr)), dfs(grid, i, j - 1, v, h, flagArr)), dfs(grid, i, j + 1, v, h, flagArr))
    } else {
        return 0
    }
}

你期待的结果是什么？实际看到的错误信息又是什么？

针对测试用例
[[1,0,7,0,0,0],[2,0,6,0,1,0],[3,5,6,7,4,2],[4,3,1,0,2,0],[3,0,5,0,20,0]]
我的输出为 58， 而实际答案为60，不知道是我哪一步没考虑周全，求大神赐教（可直接复制到leetcode该题目下方便大神调试）

Answer 1

        flagArr[i][j] = 1
        return grid[i][j] + Math.max(Math.max(Math.max(dfs(grid, i - 1, j, v, h, flagArr), dfs(grid, i + 1, j, v, h, flagArr)), dfs(grid, i, j - 1, v, h, flagArr)), dfs(grid, i, j + 1, v, h, flagArr))

flagArr 共享的。
dfs(grid, i - 1, j, v, h, flagArr)会把flagArr[i-1][j]（以及其它许多）置为1，然后后续的三个就再也不会遍历这些格子了（因为已经是1）。

在返回之前把 flagArr[i][j] 清掉应该可以解决这个问题。

        flagArr[i][j] = 1
        let r = grid[i][j] + Math.max(Math.max(Math.max(dfs(grid, i - 1, j, v, h, flagArr), dfs(grid, i + 1, j, v, h, flagArr)), dfs(grid, i, j - 1, v, h, flagArr)), dfs(grid, i, j + 1, v, h, flagArr))
        flagArr[i][j] = 0
        return r