[数据结构与算法]1219. 黄金矿工

Question

1219. 黄金矿工

Ideas

这个题很像之前的迷宫，把所有情况遍历（深度优先搜索，属于图算法的一种，英文缩写为DFS即Depth First Search.其过程简要来说是对每一个可能的分支路径深入到不能再深入为止，而且每个节点只能访问一次.）后找一个黄金量最大的即可

Code

class Solution:
    def getMaximumGold(self, grid: List[List[int]]) -> int:
        m, n = len(grid), len(grid[0])
        def dfs(i, j, gold):
            self.res = max(self.res, gold)   #更新ret
            temp = grid[i][j]
            grid[i][j] = 0     #修改当前值为0，避免走回头路
            for x, y in [(i-1,j),(i+1,j),(i,j-1),(i,j+1)]:
                if 0 <= x < m and 0 <= y < n and grid[x][y] != 0:
                    dfs(x, y, gold + grid[x][y])
            grid[i][j] = temp  #恢复回去
        
        self.res = 0
        for i in range(m):
            for j in range(n):
                if grid[i][j]:
                    dfs(i, j, grid[i][j])
        
        return self.res