[LeetCode] 1219. Path with Maximum Gold

In a gold mine grid of size m * n, each cell in this mine has an integer representing the amount of gold in that cell, 0 if it is empty.

Return the maximum amount of gold you can collect under the conditions:
Every time you are located in a cell you will collect all the gold in that cell.
From your position you can walk one step to the left, right, up or down.
You can’t visit the same cell more than once.
Never visit a cell with 0 gold.
You can start and stop collecting gold from any position in the grid that has some gold.
Example 1:

Input: grid = [[0,6,0],[5,8,7],[0,9,0]]
Output: 24
Explanation:
[[0,6,0],
[5,8,7],
[0,9,0]]
Path to get the maximum gold, 9 -> 8 -> 7.
Example 2:

Input: grid = [[1,0,7],[2,0,6],[3,4,5],[0,3,0],[9,0,20]]
Output: 28
Explanation:
[[1,0,7],
[2,0,6],
[3,4,5],
[0,3,0],
[9,0,20]]
Path to get the maximum gold, 1 -> 2 -> 3 -> 4 -> 5 -> 6 -> 7.
Constraints:

1 <= grid.length, grid[i].length <= 15
0 <= grid[i][j] <= 100
There are at most 25 cells containing gold.

黄金矿工。

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

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

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

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/path-with-maximum-gold
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

思路

思路是回溯 backtracking。注意题目里面的几个条件。既然问的是最大受益，所以二维数组每个坐标你都需要做回溯，以判断到底从哪个坐标开始挖矿的收益最大。写回溯函数的时候，注意处理越界以及当前 cell 值为 0 的情况。遇到 cell 值为 0，直接返回 0，因为这个地方按照题意你是不能访问/开采的。对于一般情况，你需要看一下四个方向往下回溯哪一个方向的收益最大，返回那个最大的收益。同时既然是回溯，在回溯的最后记得把修改过的 cell 值再改回来。

复杂度

时间O(k * 4 * 3 ^ (k - 1)) = O(4 * 3 ^ k) - 你最多有K个cell需要作为起点去访问，对于每个cell你最多有四种情况需要判断，但是对于下一个cell你只需要判断三种情况
空间O(k) - 回溯使用到的栈空间

代码

Java实现

class Solution {
    int m;
    int n;

    public int getMaximumGold(int[][] grid) {
        // corner case
        if (grid == null || grid.length == 0) {
            return 0;
        }

        // normal case
        m = grid.length;
        n = grid[0].length;
        int res = 0;
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (grid[i][j] != 0) {
                    res = Math.max(res, dfs(grid, i, j));
                }
            }
        }
        return res;
    }

    private int dfs(int[][] grid, int i, int j) {
        // 越界处理和当cell值为0的时候不visit
        if (i < 0 || j < 0 || i >= m || j >= n || grid[i][j] == 0) {
            return 0;
        }

        int origin = grid[i][j];
        // mark as 0 after visited
        grid[i][j] = 0;
        int up = dfs(grid, i, j - 1);
        int down = dfs(grid, i, j + 1);
        int left = dfs(grid, i - 1, j);
        int right = dfs(grid, i + 1, j);
        int max = Math.max(left, Math.max(right, Math.max(up, down)));
        // 还原
        grid[i][j] = origin;
        return grid[i][j] + max;
    }
}