C++使用回溯法解决黄金矿工问题

目录

• 题目描述
• 示例
• 解题思路

顺心的人大抵一样，坎坷的人各有各的坎坷。也只能坚持自我修行，等待自己的机遇。

题目描述

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

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

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

链接：https://leetcode.cn/problems/path-with-maximum-gold （力扣）

示例

解题思路

这是一道典型的矩阵 回溯 的题目，依旧是回溯三步走：

1. 回溯函数参数：

• int[][] grid 表示金矿的矩阵
• int gold 表示当前路径收集到的金子的总和
• int x, int y 表示收集到了第 grid[x][y] 位置

下面让我们来思考一个问题：本题需要建立一个 boolean[][] used 备忘录嘛？

备忘录是一定需要的，但是对本题来说，可以通过把已经遍历过的 grid[x][y] 的值改为 0，以此来实现备忘录，这样更能节省空间。

2. 结束条件：

当前遍历位置（x，y）越界，或者当前遍历位置没有金子（grid[x][y] == 0）时，结束return。

3. 单层逻辑：

int temp = grid[x][y]; // 记录值，以便回溯时恢复
gold += grid[x][y]; // 将当前值加入 gold 和中
max = Math.max(max, gold); // 更新结果
grid[x][y] = 0; // 将 grid[x][y] 置为0，防止出现同一重复重复使用

然后递归调用4次 dfs（）函数，分布对应从 （x，y）向上下左右前进

回溯部分：

grid[x][y] = temp; // 回溯，恢复 grid[x][y] 

代码：

class Solution {
    int max = Integer.MIN_VALUE;
    public int getMaximumGold(int[][] grid) {
        for(int i=0; i<grid.length; i++){
            for (int j=0; j<grid[0].length; j++){
                if(grid[i][j] != 0) { // 从每个非0位置都可以开始
                    dfs(grid, 0, i, j);
                }
            }
        }
        return max==Integer.MIN_VALUE?0:max;
    }
    public void dfs(int[][] grid, int gold, int x, int y){
        if(!isOk(grid, x, y)){ // 判断是否越界或到无金子位置，结束
            return;
        }
        int temp = grid[x][y];
        gold += grid[x][y];
        max = Math.max(max, gold); // 更新最大值
        grid[x][y] = 0; // 防止出现重复遍历
        dfs(grid, gold, x+1, y); //向上
        dfs(grid, gold, x-1, y); //向下
        dfs(grid, gold, x, y+1); //向左
        dfs(grid, gold, x, y-1); // 向右
        grid[x][y] = temp; // 回溯
    }
	// 判断是否越界 或 走到了无金子位置
    public boolean isOk(int[][] grid, int x, int y){
        if(x<0 || x>=grid.length || y<0 || y>=grid[0].length || grid[x][y] == 0){
            return false;
        }
        return true;
    }
}

本题类似的题还有岛屿问题，可以移步到 岛屿问题

到此这篇关于C++使用矩阵回溯法解决黄金矿工问题的文章就介绍到这了,更多相关C++黄金矿工内容请搜索我们以前的文章或继续浏览下面的相关文章希望大家以后多多支持我们！