每日一题之黄金矿工

题目1219：黄金矿工

你要开发一座金矿，地质勘测学家已经探明了这座金矿中的资源分布，并用大小为 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 个单元格中有黄金。

分析

这题比较简单，很明显是个回溯类型题，在当前节点可以向上下左右四个方向移动计算黄金总和，遇到为0的或者已经走过的网格则停止移动，但由于题目说矿工可以从任一网格开始，所以在最开始需要写个两层循环从任一节点开始深度计算。

代码

class Solution {
public:
    int left[4] = {1, -1, 0, 0};
    int right[4] = {0, 0, 1, -1};

    int ret = 0;

    void dfs(vector<vector<int>> &grid, vector<vector<bool>> &used, int i, int j, int tem) {
        ret = max(ret, tem);
        int row = grid.size();
        int col = grid[0].size();
        for (int k = 0; k < 4; ++k) {
            int ii = i + left[k];
            int jj = j + right[k];
            if (ii < 0 || jj < 0 || ii >= row || jj >= col) continue;
            if (grid[ii][jj] == 0 || used[ii][jj]) continue;
            used[ii][jj] = true;
            dfs(grid, used, ii, jj, tem + grid[ii][jj]);
            used[ii][jj] = false;
        }
    }

    int getMaximumGold(vector<vector<int>>& grid) {
        int row = grid.size();
        int col = grid[0].size();
        vector<vector<bool>> used;
        used.resize(row);
        for (int i = 0; i < row; ++i) {
            used[i].resize(col, false);
        }
        for (int i = 0; i < row; ++i) {
            for (int j = 0; j < col; ++j) {
                if (grid[i][j] == 0) continue;
                used[i][j] = true;
                dfs(grid, used, i, j, grid[i][j]);
                used[i][j] = false;
            }
        }
        return ret;
    }
};