JZX轻语：简

LeetCode 1219 - 黄金矿工

发表于2024年07月09日

#回溯法

此类问题均可考虑使用DFS+回溯法解决。在这道题中，以每一个有黄金的点为起点，进行深度优先搜索，找到最大的路径和。在搜索过程中，由于不允许回到已经开采的点，需要记录已经访问过的点，以避免重复访问。有一个节省空间的trick，即在访问过一个点后，将其值置为0，这样就不需要额外的空间记录已经访问过的点，待回溯结束后，将其值恢复即可。

上述节省空间的trick可以更形象地理解为，将已经访问过的点视为已经开采过的金矿，将其值置为0，表示此点无矿，不能再次访问。在回溯结束后，将其值恢复，表示金矿又重新出现，可以再次开采。

class Solution:
    moves = ((-1, 0), (1, 0), (0, -1), (0, 1))

    def getMaximumGold(self, grid: List[List[int]]) -> int:
        ans = 0
        m, n = len(grid), len(grid[0])

        def dfs(r: int, c: int, val: int):
            nonlocal ans
            ans = max(ans, val)
            orig = grid[r][c]
            grid[r][c] = 0

            for move in self.moves:
                nr = r + move[0]
                nc = c + move[1]
                if 0 <= nr < m and 0 <= nc < n and grid[nr][nc]:
                    dfs(nr, nc, val + grid[nr][nc])

            grid[r][c] = orig

        for i in range(m):
            for j in range(n):
                if grid[i][j]:
                    dfs(i, j, grid[i][j])
        return ans

闪念标签：LC

题目链接：https://leetcode.cn/problems/path-with-maximum-gold/