你要开发一座金矿，地质勘测学家已经探明了这座金矿中的资源分布，并用大小为 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 <= 150 <= 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;
}
};代码精进之路
代码精进之路，我们一起成长！