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

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