LeetCode刷题--- 黄金矿工
2023-12-31 09:38:46
个人主页:元清加油_【C++】,【C语言】,【数据结构与算法】-CSDN博客
个人专栏
力扣递归算法题
【C++】? ??
??????http://t.csdnimg.cn/6AbpV
数据结构与算法
?????http://t.csdnimg.cn/hKh2l
前言:这个专栏主要讲述递归递归、搜索与回溯剪枝算法,所以下面题目主要也是这些算法做的 ?
我讲述题目会把讲解部分分为3个部分:
1、题目解析
2、算法原理思路讲解
3、代码实现
黄金矿工
题目链接:黄金矿工
题目
你要开发一座金矿,地质勘测学家已经探明了这座金矿中的资源分布,并用大小为?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
?的单元格。 - 矿工可以从网格中?任意一个?有黄金的单元格出发或者是停止。
算法原理思路讲解
算法思路
枚举矩阵中所有的位置当成起点,来?次深度优先遍历,统计出所有情况下能收集到的??数的最大值即可。
设计代码
(1)全局变量
int ret;
bool visit[16][16];
int dx[4] = { 0, 0, -1, 1 };
int dy[4] = { 1, -1, 0, 0 };
- ret(最大的值)
- visit(二位数组中的元素是否被用过)
- dx[4](用于计算)
- dy[4](用于计算)
(2)设计递归函数
void dfs(vector<vector<int>>& grid, int x, int y, int path);
- 参数:x(当前需要进?处理的元素横坐标),y(当前需要进?处理的元素横坐标),path(当前已经处理的元素值得和);
- 返回值:无?;
- 函数作用:判断当前坐标的元素作为字符串中下标的元素出现时,向四个?向传递,查找最大值
递归过程
- 遍历每个位置,标记当前位置并将当前位置的数字作为?字?进?递归,并且在回溯时撤回标记。
- 在每个递归的状态中,我们维护?个步数 path,表?当前已经处理了数字的和·。
- 若下一个的数字为0,则不向下递归。
- 对当前位置的上下左右四个相邻位置进?递归,找出最大的路径值。
代码实现
- 时间复杂度:爆搜复杂度为指数级别,分析时空复杂度意义不大
- 空间复杂度:爆搜复杂度为指数级别,分析时空复杂度意义不大
class Solution {
public:
int ret;
bool visit[16][16];
int dx[4] = { 0, 0, -1, 1 };
int dy[4] = { 1, -1, 0, 0 };
void dfs(vector<vector<int>>& grid, int x, int y, int path)
{
ret = max(ret, path);
int m = grid.size();
int n = grid[0].size();
for (int i = 0; i < 4; i++)
{
int x1 = x + dx[i], y1 = y + dy[i];
if (x1 >= 0 && x1 < m && y1 >= 0 && y1 < n &&!visit[x1][y1] && grid[x1][y1] != 0)
{
visit[x1][y1] = true;
dfs(grid, x1, y1, path + grid[x1][y1]);
visit[x1][y1] = false;
}
}
}
int getMaximumGold(vector<vector<int>>& grid)
{
for (int i = 0; i < grid.size(); i++)
{
for (int j = 0; j < grid[i].size(); j++)
{
if (grid[i][j] != 0)
{
visit[i][j] = true;
dfs(grid, i, j, grid[i][j]);
visit[i][j] = false;
}
}
}
return ret;
}
};
文章来源:https://blog.csdn.net/weixin_74268082/article/details/135313008
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。 如若内容造成侵权/违法违规/事实不符,请联系我的编程经验分享网邮箱:veading@qq.com进行投诉反馈,一经查实,立即删除!
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。 如若内容造成侵权/违法违规/事实不符,请联系我的编程经验分享网邮箱:veading@qq.com进行投诉反馈,一经查实,立即删除!