当前位置:网站首页>模拟卷Leetcode【普通】1219. 黄金矿工
模拟卷Leetcode【普通】1219. 黄金矿工
2022-07-06 06:15:00 【邂逅模拟卷】
汇总:模拟卷Leetcode 题解汇总
1219. 黄金矿工
你要开发一座金矿,地质勘测学家已经探明了这座金矿中的资源分布,并用大小为 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 个单元格中有黄金。
来源:力扣(LeetCode)
链接:https://leetcode-cn.com/problems/path-with-maximum-gold
著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。
代码:
from leetcode_python.utils import *
class Solution:
def __init__(self):
self.res = 0
@lru_cache(None)
def next(self,rowid,colid):
res = []
for i, j in ((rowid - 1, colid), (rowid, colid - 1), (rowid + 1, colid), (rowid, colid + 1)):
if 0 <= i < self.height and 0 <= j < self.width:
res.append([i, j])
return res
def dfs(self,r,c,now):
g = self.grid[r][c]
now+=g
self.res = max(self.res,now)
self.grid[r][c]=0
for nextr,nextc in self.next(r,c):
if self.grid[nextr][nextc]:
self.dfs(nextr,nextc,now)
self.grid[r][c]=g
def getMaximumGold(self, grid: List[List[int]]) -> int:
self.grid = grid
self.height,self.width = len(grid), len(grid[0])
for i in range(self.height):
for j in range(self.width):
if grid[i][j]:
self.dfs(i,j,0)
return self.res
def test(data_test):
s = Solution()
data = data_test # normal
# data = [list2node(data_test[0])] # list转node
return s.getMaximumGold(*data)
def test_obj(data_test):
result = [None]
obj = Solution(*data_test[1][0])
for fun, data in zip(data_test[0][1::], data_test[1][1::]):
if data:
res = obj.__getattribute__(fun)(*data)
else:
res = obj.__getattribute__(fun)()
result.append(res)
return result
if __name__ == '__main__':
datas = [
[
[[0,6,0],[5,8,7],[0,9,0]]],
]
for data_test in datas:
t0 = time.time()
print('-' * 50)
print('input:', data_test)
print('output:', test(data_test))
print(f'use time:{
time.time() - t0}s')
备注:
GitHub:https://github.com/monijuan/leetcode_python
CSDN汇总:模拟卷Leetcode 题解汇总
可以加QQ群交流:1092754609
leetcode_python.utils详见汇总页说明
先刷的题,之后用脚本生成的blog,如果有错请留言,我看到了会修改的!谢谢!
边栏推荐
- Idea new UI usage
- leaflet 地图
- 「 WEB测试工程师 」岗位一面总结
- Caused by:org.gradle.api.internal.plugins . PluginApplicationException: Failed to apply plugin
- The ECU of 21 Audi q5l 45tfsi brushes is upgraded to master special adjustment, and the horsepower is safely and stably increased to 305 horsepower
- LeetCode 739. 每日温度
- GTSAM中ISAM2和IncrementalFixedLagSmoother说明
- D - How Many Answers Are Wrong
- Embedded point test of app
- 联合索引的左匹配原则
猜你喜欢
Pat (Grade B) 2022 summer exam
数据库隔离级别
Construction and integration of Zipkin and sleuth for call chain monitoring
[wechat applet] build a development tool environment
IPv6 comprehensive experiment
Understanding of processes and threads
The latest 2022 review of "graph classification research"
B - The Suspects
全程实现单点登录功能和请求被取消报错“cancelToken“ of undefined的解决方法
Summary of anomaly detection methods
随机推荐
LeetCode 732. 我的日程安排表 III
自定义指定路由上的Gateway过滤器工厂
Eigen sparse matrix operation
Construction and integration of Zipkin and sleuth for call chain monitoring
[C language] string left rotation
On weak network test of special test
Manhattan distance and Manhattan rectangle - print back font matrix
Isam2 operation process
Summary of anomaly detection methods
[eolink] PC client installation
Usage of test macro of GTEST
Clock in during winter vacation
Database - current read and snapshot read
Web界面元素的测试
LeetCode 729. 我的日程安排表 I
Database isolation level
IP day 16 VLAN MPLS configuration
Idea new UI usage
P问题、NP问题、NPC问题、NP-hard问题详解
Application du Groupe Li dans gtsam