Leetcode 1219:黄金矿工(超详细的解法!!!)
发布日期:2021-06-29 15:56:36
浏览次数:2
分类:技术文章
本文共 1426 字,大约阅读时间需要 4 分钟。
你要开发一座金矿,地质勘测学家已经探明了这座金矿中的资源分布,并用大小为 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 个单元格中有黄金。
解题思路
典型的dfs
问题,通过遍历grid
,判断当期的值是不是大于0
,如果是的话,那么我们可以开始挖掘。接着思路就是dfs
了,遍历的过程中,对于遍历过的区域将它标记为0
即可。
class Solution: def getMaximumGold(self, grid: List[List[int]]) -> int: m, n = len(grid), len(grid[0]) d = [(0, 1), (1, 0), (0, -1), (-1, 0)] def dfs(x, y): res = 0 src = grid[x][y] grid[x][y] = 0 for i, j in d: nx = i + x ny = j + y if nx >= 0 and nx < m and ny >= 0 and ny < n and grid[nx][ny] != 0: res = max(res, grid[nx][ny] + dfs(nx, ny)) grid[x][y] = src return res res = 0 for i in range(m): for j in range(n): if grid[i][j] != 0: res = max(res, grid[i][j] + dfs(i, j)) return res
我将该问题的其他语言版本添加到了我的
如有问题,希望大家指出!!!
转载地址:https://coordinate.blog.csdn.net/article/details/102475196 如侵犯您的版权,请留言回复原文章的地址,我们会给您删除此文章,给您带来不便请您谅解!
发表评论
最新留言
关注你微信了!
[***.104.42.241]2024年05月01日 08时05分16秒
关于作者
喝酒易醉,品茶养心,人生如梦,品茶悟道,何以解忧?唯有杜康!
-- 愿君每日到此一游!
推荐文章
JavaScript 的addEventListener() 事件监听详解!
2019-04-29
上传图片到阿里云OSS和获取上传图片的url的详解 !
2019-04-29
Kafka为什么这么快?
2019-04-29
Java 生产者和消费者面试题
2019-04-29
生产者消费者问题
2019-04-29
本机电脑连接虚拟机redis失败解决方法
2019-04-29
DM365 应用层gpio控制
2019-04-29
linux i2c子系统abc
2019-04-29
CSS3 帧动画(Sprite,直译叫雪碧图)
2019-04-29
Java 父线程与子线程相互通信的方法
2019-04-29
Redis 六种淘汰策略和三种删除策略
2019-04-29
Java LinkedHashMap
2019-04-29
JPA 多线程同时对一条数据进行Update的问题
2019-04-29
JPA 多线程对数据进行更新,Update和Insert同时存在的问题
2019-04-29
Java 高性能队列Disruptor
2019-04-29
SpringBoot 使用https
2019-04-29
Java 读写锁
2019-04-29
JVM Minor GC、Full GC和Major GC
2019-04-29
SpringBoot @Scheduled 执行两次的问题
2019-04-29
tomcat配置JVM
2019-04-29