1219. Path with Maximum Gold-黄金矿工

你要开发一座金矿，地质勘测学家已经探明了这座金矿中的资源分布，并用大小为m * n的网格grid进行了标注。每个单元格中的整数就表示这一单元格中的黄金数量；如果该单元格是空的，那么就是0。

为了使收益最大化，矿工需要按以下规则来开采黄金：

• 每当矿工进入一个单元，就会收集该单元格中的所有黄金。
• 矿工每次可以从当前位置向上下左右四个方向走。
• 每个单元格只能被开采（进入）一次。
• 不得开采（进入）黄金数目为0的单元格。
• 矿工可以从网格中任意一个有黄金的单元格出发或者是停止。
   

示例 1：

输入：grid = [[0,6,0],[5,8,7],[0,9,0]]
输出：24
解释：
[[0,6,0],
 [5,8,7],
 [0,9,0]]
一种收集最多黄金的路线是：9 -> 8 -> 7。

示例 2：

输入：grid = [[1,0,7],[2,0,6],[3,4,5],[0,3,0],[9,0,20]]
输出：28
解释：
[[1,0,7],
 [2,0,6],
 [3,4,5],
 [0,3,0],
 [9,0,20]]
一种收集最多黄金的路线是：1 -> 2 -> 3 -> 4 -> 5 -> 6 -> 7。

提示：

• 1 <= grid.length, grid[i].length <= 15
• 0 <= grid[i][j] <= 100
• 最多 25 个单元格中有黄金。

Python:

class Solution:
    def getMaximumGold(self, grid: List[List[int]]) -> int:
        def dfs(grid, i, j, temp):
            if grid[i][j] == 0:
                return temp
            value = grid[i][j]
            result = 0
            if i-1 >= 0:
                grid[i][j] = 0
                result = max(result, dfs(grid, i-1, j, temp+value))
                grid[i][j] = value
            if i+1 < len(grid):
                grid[i][j] = 0
                result = max(result, dfs(grid, i+1, j, temp+value))
                grid[i][j] = value
            if j-1 >= 0:
                grid[i][j] = 0
                result = max(result, dfs(grid, i, j-1, temp+value))
                grid[i][j] = value
            if j+1 < len(grid[0]):
                grid[i][j] = 0
                result = max(result, dfs(grid, i, j+1, temp+value))
                grid[i][j] = value
            return result
        result = 0
        for i in range(len(grid)):
            for j in range(len(grid[0])):
                result = max(result, dfs(grid, i, j, 0))
        return result

Java:

class Solution {
    public int getMaximumGold(int[][] grid) {
        int result = 0;
        for(int i = 0; i < grid.length; i++)
        {
            for(int j = 0; j < grid[0].length; j++)
            {
                if(grid[i][j] != 0)
                    result = Math.max(result, dfs(grid, i, j, 0));
            }
        }
        return result;
    }

    public int dfs(int[][] grid, int i, int j, int temp)
    {
        if(grid[i][j] == 0)
            return temp;
        int[][] arr = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
        int value = grid[i][j];
        int result = 0;
        for(int k = 0; k < 4; k++)
        {
            int ni = i+arr[k][0];
            int nj = j+arr[k][1];
            grid[i][j] = 0;
            if(ni >= 0 && ni < grid.length && nj >=0 && nj < grid[0].length) 
                result=  Math.max(result, dfs(grid, ni, nj, temp+value));
            grid[i][j] = value;
        }
        return result;
    }
}