当前位置:网站首页>模拟卷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,如果有错请留言,我看到了会修改的!谢谢!
边栏推荐
- 【Postman】动态变量(也称Mock函数)
- leaflet 地图
- B - The Suspects
- 误差的基本知识
- Software test interview questions - Test Type
- Detailed explanation of P problem, NP problem, NPC problem and NP hard problem
- Isam2 operation process
- Postman核心功能解析-参数化和测试报告
- ICLR 2022 spotlight | analog transformer: time series anomaly detection method based on correlation difference
- 还在为如何编写Web自动化测试用例而烦恼嘛?资深测试工程师手把手教你Selenium 测试用例编写
猜你喜欢
【Tera Term】黑猫带你学TTL脚本——嵌入式开发中串口自动化神技能
Understanding of processes and threads
Clock in during winter vacation
【C语言】字符串左旋
Configuring OSPF GR features for Huawei devices
技术分享 | 常见接口协议解析
[postman] collections - run the imported data file of the configuration
ESP32 ESP-IDF看门狗TWDT
Usage of test macro of GTEST
异常检测方法总结
随机推荐
Introduction to promql of # yyds dry goods inventory # Prometheus
数学三大核心领域概述:代数
Database - current read and snapshot read
Testing of web interface elements
Linux regularly backs up MySQL database
曼哈顿距离和-打印菱形
黑猫带你学UFS协议第4篇:UFS协议栈详解
Request forwarding and redirection
php使用redis实现分布式锁
Caused by:org. gradle. api. internal. plugins . PluginApplicationException: Failed to apply plugin
GTSAM中ISAM2和IncrementalFixedLagSmoother说明
Detailed explanation of BF and KMP
ICLR 2022 spotlight | analog transformer: time series anomaly detection method based on correlation difference
技术分享 | 常见接口协议解析
JWT-JSON WEB TOKEN
Hypothesis testing learning notes
Caused by:org.gradle.api.internal.plugins . PluginApplicationException: Failed to apply plugin
leaflet 地图
还在为如何编写Web自动化测试用例而烦恼嘛?资深测试工程师手把手教你Selenium 测试用例编写
MPLS test report