class Solution {
public:
int getMaximumGold(vector<vector<int>>& grid) {
}
};
1219. 黄金矿工
你要开发一座金矿，地质勘测学家已经探明了这座金矿中的资源分布，并用大小为 m * n 的网格 grid 进行了标注。每个单元格中的整数就表示这一单元格中的黄金数量；如果该单元格是空的，那么就是 0。
为了使收益最大化，矿工需要按以下规则来开采黄金：
0 的单元格。
示例 1：
输入：grid = [[0,6,0],[5,8,7],[0,9,0]] 输出：24 解释： [[0,6,0], [5,8,7], [0,9,0]] 一种收集最多黄金的路线是：9 -> 8 -> 7。
示例 2：
输入：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。
提示：
1 <= grid.length, grid[i].length <= 150 <= grid[i][j] <= 100原站题解
javascript 解法, 执行用时: 252 ms, 内存消耗: 41.4 MB, 提交时间: 2022-11-25 17:27:33
/**
* @param {number[][]} grid
* @return {number}
*/
var getMaximumGold = function(grid) {
this.grid = grid;
this.m = grid.length;
this.n = grid[0].length;
this.dirs = [[-1, 0], [1, 0], [0, -1], [0, 1]];
this.ans = 0;
const dfs = (x, y, gold, dirs) => {
gold += grid[x][y];
this.ans = Math.max(ans, gold);
const rec = grid[x][y];
grid[x][y] = 0;
for (let d = 0; d < 4; ++d) {
const nx = x + this.dirs[d][0];
const ny = y + this.dirs[d][1];
if (nx >= 0 && nx < m && ny >= 0 && ny < n && grid[nx][ny] > 0) {
dfs(nx, ny, gold);
}
}
grid[x][y] = rec;
}
for (let i = 0; i < m; ++i) {
for (let j = 0; j < n; ++j) {
if (grid[i][j] !== 0) {
dfs(i, j, 0);
}
}
}
return ans;
};
golang 解法, 执行用时: 56 ms, 内存消耗: 1.9 MB, 提交时间: 2022-11-25 17:26:36
var dirs = []struct{ x, y int }{{-1, 0}, {1, 0}, {0, -1}, {0, 1}}
func getMaximumGold(grid [][]int) (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 dirs {
nx, ny := x+d.x, y+d.y
if 0 <= nx && nx < len(grid) && 0 <= ny && ny < len(grid[nx]) && grid[nx][ny] > 0 {
dfs(nx, ny, gold)
}
}
grid[x][y] = rec
}
for i, row := range grid {
for j, gold := range row {
if gold > 0 {
dfs(i, j, 0)
}
}
}
return
}
python3 解法, 执行用时: 3892 ms, 内存消耗: 15.1 MB, 提交时间: 2022-11-25 17:26:14
class Solution:
def getMaximumGold(self, grid: List[List[int]]) -> int:
m, n = len(grid), len(grid[0])
ans = 0
def dfs(x: int, y: int, gold: int) -> None:
gold += grid[x][y]
nonlocal ans
ans = max(ans, gold)
rec = grid[x][y]
grid[x][y] = 0
for nx, ny in ((x - 1, y), (x + 1, y), (x, y - 1), (x, y + 1)):
if 0 <= nx < m and 0 <= ny < n and grid[nx][ny] > 0:
dfs(nx, ny, gold)
grid[x][y] = rec
for i in range(m):
for j in range(n):
if grid[i][j] != 0:
dfs(i, j, 0)
return ans