【2.10】回溯算法-解黄金矿工问题

本文主要是介绍【2.10】回溯算法-解黄金矿工问题，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

一、题目

二、解题思路

        这道题目要求我们在一个二维数组中，从任意位置出发，探索上下左右四个方向的路径，并找出路径上数值最大的那一条。需要注意的是，数值为0的格子视为障碍，无法通过。通过绘制一个简单的示意图，我们可以更直观地理解这一过程。

int getMaximumGold(vector<vector<int>>& grid) {// 边界条件判断if (grid.empty() || grid[0].empty())return 0;// 保存最大路径值int res = 0;// 两个for循环，遍历每一个位置，让他们当做起点// 查找最大路径值for (int i = 0; i < grid.size(); i++) {for (int j = 0; j < grid[0].size(); j++) {// 函数dfs是以坐标(i,j)为起点，查找最大路径值res = max(res, dfs(grid, i, j));}}// 返回最大路径值return res;
}

        这张图的流程会持续沿着每个分支深入，直至达到终止条件。一旦遇到终止条件，所有经过的位置都会被标记为0，以表示这些位置不能再被访问。终止条件包括：索引i和j均未超出边界，且当前位置的值不为0。判断如下：

 if (x < 0 || x >= grid.size() || y < 0 || y >= grid[0].size() || grid[x][y] == 0)return 0;

        由于采用了递归方法，在深入递归时，会将当前位置的值设为0；而在递归返回时，需要将当前位置的值恢复原状。

三、代码实现

#include <iostream>
#include <vector>
#include <algorithm>using namespace std;int dfs(vector<vector<int>>& grid, int x, int y) {// 边界条件的判断，x,y都不能越界，同时当前坐标的位置如果是0，表示有障碍物或者遍历过了if (x < 0 || x >= grid.size() || y < 0 || y >= grid[0].size() || grid[x][y] == 0)return 0;// 先把当前坐标的值保存下来，最后再还原int temp = grid[x][y];// 当前坐标已经访问过了，要把他标记为0，防止再次访问grid[x][y] = 0;// 然后沿着当前坐标的上下左右4个方向查找int up = dfs(grid, x, y - 1); // 往上找int down = dfs(grid, x, y + 1); // 往下找int left = dfs(grid, x - 1, y); // 往左找int right = dfs(grid, x + 1, y); // 往右找// 这里只要4个方向的最大值即可int maxDirection = max({left, right, up, down});// 然后再把当前位置的值还原grid[x][y] = temp;// 返回最大路径值return grid[x][y] + maxDirection;
}int getMaximumGold(vector<vector<int>>& grid) {// 边界条件判断if (grid.empty() || grid[0].empty())return 0;// 保存最大路径值int res = 0;// 两个for循环，遍历每一个位置，让他们当做起点// 查找最大路径值for (int i = 0; i < grid.size(); i++) {for (int j = 0; j < grid[0].size(); j++) {// 函数dfs是以坐标(i,j)为起点，查找最大路径值res = max(res, dfs(grid, i, j));}}// 返回最大路径值return res;
}int main() {// 示例二维数组vector<vector<int>> grid = {{0, 6, 0},{5, 8, 7},{0, 9, 0}};// 调用getMaximumGold函数并输出结果int result = getMaximumGold(grid);cout << "Maximum gold: " << result << endl;return 0;
}

这篇关于【2.10】回溯算法-解黄金矿工问题的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---