力扣每日一题2022-02-05中等题：黄金矿工

题目描述思路

回溯

Python实现Java实现

黄金矿工

首先在m*n个网格内枚举起点，只要格子内的数字大于0，即可作为起点进行开采。
记枚举的起点为(i, j)，则从(i, j)开始进行递归和回溯，枚举所有可行的开采路径。用DFS递归进行枚举，定义dfs(x, y, gold)，(x, y)表示当前位置，gold表示开采(x, y)前开采的黄金数量。根据题意，还需要做如下操作：

需要将gold维护为gold+grid[x][y]，表示对(x, y)进行开采。由于目标是最大化收益，因此还要维护一个最大的收益值ans，并在这一步使用gold更新ans；需要枚举矿工下一步的方向。由于可以往上下左右四个方向走，所以要依次枚举每个方向。如果往某个方向不会走出网格，并且走到位置的值不为0，就可以进行递归搜索，在搜索完所有方向后，进行回溯。
因为每个单元格只能被开采一次，所以当到达(x, y)时，先将grid[x][y]置为0，回溯前，再恢复。 Python实现

class Solution:
    def getMaximumGold(self, grid: List[List[int]]) -> int:
        m, n = len(grid), len(grid[0])
        ans = 0
        
        def dfs(x, y, gold):
            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

class Solution {
    static int[][] dirs = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
    int[][] grid;
    int m, n;
    int ans;
    
    public int getMaximumGold(int[][] grid) {
        this.grid = grid;
        this.m = grid.length;
        this.n = grid[0].length;
        for (int i = 0; i < m; ++i) {
            for (int j = 0; j < n; ++j) {
                if (grid[i][j] > 0) {
                    dfs(i, j, 0);
                }
            }
        }
        return ans;
    }
    
    private void dfs(int x, int y, int gold) {
        gold += grid[x][y];
        ans = Math.max(ans, gold);
        int rec = grid[x][y];
        grid[x][y] = 0;
        for (int d = 0; d < 4; ++d) {
            int nx = x + dirs[d][0];
            int ny = y + dirs[d][1];
            if (nx >= 0 && nx < m && ny >= 0 && ny < n && grid[nx][ny] > 0) {
                dfs(nx, ny, gold);
            }
        }
        
        grid[x][y] = rec;
    }
}