提供了编程的基础技术教程

zl程序教程

您现在的位置是：首页 >  Java

当前栏目

菜鸟的每日力扣系列——1219. 黄金矿工（#Day29）

2023-02-18 16:23:57 时间

力扣1219. 黄金矿工

这道题目与我们在4399上玩的黄金矿工不同，它的规则如下：

  1. 黄金数为0的点不能进入
  2. 每个位置进入后不能重复进入
  3. 每个位置的黄金一次性收齐
  4. 矿工可以从任意不为0的位置进入
  5. 矿工可以上下左右四个方向走

对于行进路线的问题一般考虑dfs和bfs来解。通常对于涉及步数最多或者最少用bfs；涉及总量最多或最少使用dfs。这道题的结果是要收集最多的黄金，所以采用dfs广度优先遍历。

确定好方法，代码具体实现思路可以是这样：

  1. 首先记录矩形的长和宽，初始化最终黄金数为0；
  2. 遍历每个位置，如果该位置有黄金可以进入，进行dfs；
  3. 从起点出发，如果有更好的路径，替换掉原路径和最大黄金数；
  4. 走过的位置标为0，尝试完这条路经后再恢复为原值；
  5. 在有下一个位置的情况下，叠加计算最大黄金数，确定是否是最佳路径。 
from typing import List


def getMaximumGold(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]  # gold用来存放已有黄金数，初始为0
        nonlocal ans
        ans = max(ans, gold)  # 黄金数大于当前结果，更新总数
        tmp = grid[x][y]
        grid[x][y] = 0  # 第一次到达这个位置，先置为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] = tmp  # 将尝试过的位置再恢复成原来的值
    for i in range(m):
        for j in range(n):
            if grid[i][j] != 0:  # 位置没有黄金无法进入
                dfs(i, j, 0)
    return ans


grid = [[0, 6, 0], [5, 8, 7], [0, 9, 0]]
print(getMaximumGold(grid))  # 24

END

相关文章