LeetCode刷题--- 黄金矿工

2023-12-31 09:38:46

个人主页:元清加油_【C++】,【C语言】,【数据结构与算法】-CSDN博客

个人专栏

力扣递归算法题

?http://t.csdnimg.cn/yUl2I

【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(当前已经处理的元素值得和);
  • 返回值:无?;
  • 函数作用:判断当前坐标的元素作为字符串中下标的元素出现时,向四个?向传递,查找最大值

递归过程

  1. 遍历每个位置,标记当前位置并将当前位置的数字作为?字?进?递归,并且在回溯时撤回标记。
    1. 在每个递归的状态中,我们维护?个步数 path,表?当前已经处理了数字的和·。
    2. 若下一个的数字为0,则不向下递归。
  2. 对当前位置的上下左右四个相邻位置进?递归,找出最大的路径值。


代码实现

  • 时间复杂度:爆搜复杂度为指数级别,分析时空复杂度意义不大
  • 空间复杂度:爆搜复杂度为指数级别,分析时空复杂度意义不大
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
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。