【回溯】黄金矿工，你小时候玩过吗?!!

利刃大大

发布于 2025-02-08 14:09:12

4100

代码可运行

文章被收录于专栏：csdn文章搬运csdn文章搬运

运行总次数：0

代码可运行

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 个单元格中有黄金。

解题思路：深度优先遍历

这道题其实也不难，就是一个深度优先遍历，不过题目说明矿工可以从网格中任意一个有黄金的单元格出发或者是停止，所以我们需要遍历每个节点作为入口的情况，所以就需要在 getMaximumGold() 函数中进行所有元素的枚举，然后直接调用递归函数替我们去完成任务，最后返回全局变量 ret 即可，ret 就是存放结果集的，表示当前开采的最大黄金数量！

而递归函数中无非就是三步走：

函数头的设计：

首先少不了的就是题目给的网格 grid。

此外因为我们需要判断当前位置是否越界，所以需要有当前位置在网格中的坐标，所以需要 x 和 y 来表示！

然后我们还要搞个变量 cur 来记录当前已经开采的黄金数量，如果弄成全局变量也是可以的，只不过需要在回溯处理的时候多处理一下就行，不过这里作为函数参数传递的话就少个这个回溯处理了！

void dfs(vector<vector<int>>& grid, int x, int y, int cur);

递归函数出口：

因为这道题要求说同一个单元格内的字母不允许被重复使用，所以我们需要一个 全局的布尔类型二维数组 used 来标记当前位置是否已经走过，这样子往下的路径就能知道哪些该走哪些不该走！

然后主要就是判断以下内容：

当前在网格中的坐标是不是越界了
当前元素是否已经走过了
当前元素是否为 0

如果出现其中一个不符合的话，则直接 return false 即可！

// 递归函数出口
if(x < 0 || x == grid.size() || y < 0 || y == grid[x].size() || used[x][y] == true || grid[x][y] == 0)
	return;

函数体的内容：

函数体要做的事情无非就是进行处理当前元素、递归、回溯操作。
- 其中处理当前元素对于这道题来说就是标记进行当前元素已经走过，也就是将 used[x][y] = true，然后还需要累加一下 cur，此时再尝试更新一下 ret，如果遇到更大的那么它就记录下更大的数值了！
- 递归处理的话，就是上下左右去递归即可，也不需要关心是否走到重复的位置，因为在递归出口处我们已经进行了限制！
- 对于回溯操作的话，这里需要将 used[x][y] = false，然后就不需要处理其它问题了，因为其它变量对其它层没有影响，是局部的！

class Solution {
private:
    int ret;           // 存放结果集，表示当前开采的最大黄金数量
    bool used[15][15]; // 标记当前元素是否已经走过，true表示走过
public:
    int getMaximumGold(vector<vector<int>>& grid) {
        // 遍历每个节点作为入口的情况
        for(int i = 0; i < grid.size(); ++i)
            for(int j = 0; j < grid[i].size(); ++j)
                dfs(grid, i, j, 0);
        return ret;
    }

    void dfs(vector<vector<int>>& grid, int x, int y, int cur)
    {
        // 函数递归出口
        if(x < 0 || x == grid.size() || y < 0 || y == grid[x].size() || used[x][y] == true || grid[x][y] == 0)
            return;
        
        // 处理当前节点
        cur += grid[x][y];
        ret = max(cur, ret); // 让ret尝试更新最大值
        used[x][y] = true;
		
        // 递归处理
        dfs(grid, x + 1, y, cur);
        dfs(grid, x - 1, y, cur);
        dfs(grid, x, y + 1, cur);
        dfs(grid, x, y - 1, cur);
		
        // 回溯操作（只需要处理used数组，而cur是局部变量，不需要关心对其它层的影响）
        used[x][y] = false;
    }
};

本文参与腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。

原始发表：2025-02-07，如有侵权请联系 cloudcommunity@tencent.com 删除

遍历